codeforce：G. Good Key, Bad Key【贪心】

分析

有两个操作，我们不知道选哪个
我们就考虑先a后b和先b后a
# x y
# good and bad: x + y // 2 - k
# bad and good: x // 2 + y // 2 - k
# thus, after bad no good
# 2 ^ 30 > 10 ** 9, at most 30 bad

因此，bad后面根good都是不好的
所以bad后面继续根bad，最多30个，后面全0

ac code

import sys
input = sys.stdin.readline

for _ in range(int(input())):
    n, k = list(map(int, input().split()))
    a = list(map(int, input().split()))
    # x y
    # good and bad: x + y // 2 - k
    # bad and good: x // 2 + y // 2 - k
    # thus, after bad no good
    # 2 ^ 30 > 10 ** 9, at most 30 bad
    maxn = 0
    nowSum = 0
    for i in range(n):
        badSum = nowSum
        cnt = 0
        while cnt < 32 and i + cnt < n:
            badSum += a[i + cnt] // (2 ** (cnt + 1))
            cnt += 1
        maxn = max(maxn, badSum)
        nowSum += a[i] - k # goodSum

    maxn = max(maxn, nowSum)
    print(maxn)

总结

发现了bad后面不能根good就贪心搞定了