当前位置：网站首页>codeforce：G. Good Key, Bad Key【贪心】

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

2022-07-17 18:13:00 【白速龙王的回眸】

在这里插入图片描述

分析

有两个操作，我们不知道选哪个
我们就考虑先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)