每日一题 | 不确定参与人数的抽奖问题

2020-08-04 13:52:31

昨日问题

每日一题 | 两个序列归并问题

题目同样源于codeforces，链接：https://codeforces.com/gym/102646/problem/B

这是一道经典的贪心问题，由于我们可以随意地从A和B中获取元素，我们又希望得到的结果的字典序小。我们很容易分析出要尽量将小的元素放在前面，而大的元素放在后面。

基于这样的原理，我们很容易想到算法，可以用两个指针分别指向A和B的开头。每次都选择其中较小的那一个。比如1 3 5和2 4 6，一开始是1和2比，由于1小于2，所以选择1。A的指针移动一位指向3，下一轮比较3和2，由于2小于3，所以选择2。如此循环往复直到所有元素都被取完为止。

我们观察一下样例，这个算法都可以支持。

但是这里藏了一个trick，如果A和B的元素相等，那么应该怎么办呢？是随便取哪个都行吗，还是？

比如A是3 3 3 1，B是3 3 3 4，这个时候还能随意取吗？显然不能，因为A中的第四个元素是1，小于B中第四个元素4。所以应该先取A中的3，也就是说当A和B头部的元素相等的时候，我们应该继续往后比较，直到出现元素不同的情况为止，然后我们选择较小的那个。

这段代码并不难写：

import sys


n = int(input())

A = list(map(int, input().split(' ')))
B = list(map(int, input().split(' ')))

# 插入无穷大，作为标兵，防止超界
A.append(sys.maxsize)
B.append(sys.maxsize)

C = []

ida, idb = , 

for i in range(2*n):
    if A[ida] < B[idb]:
        C.append(A[ida])
        ida += 1
    elif A[ida] > B[idb]:
        C.append(B[idb])
        idb += 1
    else:
        # 如果相等往后比较
        ca, cb = ida+1, idb+1
        while A[ca] == B[cb] and ca <= n and cb <= n:
            ca += 1
            cb += 1
        if A[ca] < B[cb]:
            C.append(A[ida])
            ida += 1
        else:
            C.append(B[idb])
            idb += 1


for i in C:
    print(i, end=' ')