4.10 百度笔试记录

百度太奇怪了，我3月7号投了简历，第一次笔试我有别的事放弃了，然后就一直没有再通知我笔试了，上周给HR发了一下邮件才赶上最后一次笔试。开个帖子记录一下今晚的编程题吧。

第一题太简单了就不po了，第二题大概是：有n个士兵，nums[i]代表第i个士兵的战斗值，小明和小红给士兵排序，两人共进行m次操作，小明每次操作会选择一个k，将前k个士兵从小到大排序；小红每次操作选择一个k，将前k个士兵从大到小排序，输出全部操作结束后士兵的战斗值。m和n的数量级在10^5。

简述一下思路，如果暴力的方法的话，复杂度是O(mnlogn)，过不了；一个优化的方法是，一个操作的k如果大于等于它之前的操作的k，那之前的操作可以忽略，所以一个比较显然的思路是用单调栈来优化，用代码来解释吧，复杂度是O(nlogn + m)

n, m = map(int, input().split())
nums = list(map(int, input().split())) # 战斗值
stack, ans = [], []
for _ in range(m):
    p, k = map(int, input().split()) # p=1:小明操作；p=2:小红
    while stack and stack[-1][-1] <= k:
        stack.pop()
    stack.append((p, k))
stack.append((0, 0))
maxk, l, r = stack[0][1], 0, -1
lst = sorted(nums[:maxk])
for i in range(len(stack) - 1):
    length = stack[i][1] - stack[i + 1][1]
    if stack[i][0] == 1:
        ans.extend(lst[r:r - length:-1])
        r -= length
    elif stack[i][0] == 2:
        ans.extend(lst[l:l + length])
        l += length
ans = ans[::-1] + nums[maxk:]
print(*ans)