Q1 100%

题意

小昱购买了两款游戏，第一款游戏***有n个关卡，通过第i关需要花ai的时间；第二款游戏***有m个关卡，通过第i关需要花bi的时间。两款游戏都不允许跳过关卡，即必须要通过第i关，才能挑战第i+1关。小昱想知道在游戏时长不超过t的情况下，最多可以通过多少关？

输入

第一行 n,m,t
第二行 ai数组
第三行 bi数组

思路

前缀和加枚举通过第一关的游戏数，更新答案。 具体实现可以写二分（见代码），注意到前缀和具有单调性所以也可以写双指针。

def solve():
    n, m, t = map(int, input().split())
    *a, = map(int, input().split())
    *b, = map(int, input().split())
    if n > m:
        n, m = m, n 
        a, b = b, a
    presum1 = [0] * (n + 1)
    presum2 = [0] * (m + 1)
    for i in range(1, n + 1):
        presum1[i] = presum1[i - 1] + a[i - 1]
    for i in range(1, m + 1):
        presum2[i] = presum2[i - 1] + b[i - 1]

    def find(target):
        l = 0
        r = m
        index = -1
        while l <= r:
            mid = (l + r) // 2
            if presum2[mid] <= target:
                index = mid 
                l = mid + 1
            else:
                r = mid - 1
        return index
    res = 0
    for i in range(n + 1):
        remain = t - presum1[i]
        if remain < 0:
            return res
        else:
            t2 = find(remain)
            if t2 + i > res:
                res = t2 + i 
    return res

print(solve())

Q2 100%

题意

小明买了一些玩具士兵，他邀请小红一起玩。他总共有n个士兵，刚开始时，这n个士兵被排成一列，第i个士兵的战斗力为hi。然后小明和小红开始给它们排序。二人总共进行了m次操作。小明的每次操作会选择一个数k，将前k个士兵按战斗力从小到大排序。小红的每次操作会选择一个数k，将前k个士兵按战斗力从大到小排序。请问所有操作结束后从前往后每个士兵的战斗力是多少？

输入

第一行 n, m
第二行 长度为n的数组
后m行 tmp, k (tmp 等于1 代表小明， tmp 等于2 代表小红)

思路

• 注意到当后面的k大于等于前面的k时候，前面的操作变成无效操作
• 如果是同一个人连续操作，那么后面的k小于前面的k时候，操作无效
• 因此，先用单调栈找到有效操作 按照题意模拟即可 具体实现可以加哨兵优化 笔试的时候写的不是很优雅 应该有更优雅的写法

def solve():
    n, m = map(int, input().split())
    *nums, = map(int, input().split())
    stack = []
    for i in range(m):
        pid, k = map(int, input().split())
        while stack and k >= stack[-1][0]:
            stack.pop() 
        if stack and stack[-1][1] == pid:
            continue 
        stack.append([k, pid])
    res = nums[:]
    if stack:
        candidates = nums[:stack[0][0]]
        l = 0
        r = len(candidates) - 1
        candidates.sort()
        for i in range(len(stack) - 1):
            tmp = stack[i][0] - stack[i + 1][0]
            if stack[i][1] == 1:
                res[stack[i + 1][0]: stack[i][0]] = candidates[r - tmp + 1 : r + 1]
                r -= tmp
            else:
                res[stack[i + 1][0]: stack[i][0]] = candidates[l : l + tmp][::-1]
                l += tmp 
        if stack[-1][1] == 1:
            res[:stack[-1][0]] = candidates[l:r + 1]
        else:
            res[:stack[-1][0]] = candidates[l:r + 1][::-1]

    return " ".join(map(str, res))
print(solve())