题面描述:

某公司为新用户推出大礼包，用户从任意一天注册后，可以连续登录$x$天并领取金币。金币数量与一年中$n$个月的日历相关，每个月第一天得1个金币，第二天得2个金币，以此类推。输入包含月数$n$和连续登录天数$x$，以及每个月的天数$d_1, d_2, \ldots, d_n$。要求计算用户在注册后连续登录$x$天，最多可以获得的金币总数，且连续登录可能跨年。

题解

塔子哥希望找到连续 x 天内可以获得最多金币的方案。为了实现这一目标，我们的日历数据是一个长度为 n 的数组 d，其中每个元素表示每个月的天数。由于塔子哥可以跨越到下一年的第一个月，因此我们需要考虑跨年情况。为了解决这个问题，我们采用了以下思路：

1. 双倍日历数组：将日历数组 d 复制一份，形成一个长度为 2n 的数组。这一做法确保我们可以在任何地方找到长度为 x 的连续天数，并且能够平滑地处理跨年情况。

2. 滑动窗口算法：我们通过滑动窗口的方式来计算在不同起点下，连续 x 天可以获得的金币总数。窗口的初始位置从 0 开始，每次移动一格，尝试不同的起点。

3. 动态调整窗口：在窗口滑动过程中，维护当前窗口中的天数和金币总和。如果当前窗口内的天数和大于 x，则从左侧移除天数，直到窗口中的天数和小于等于 x。

4. 计算金币总数：当窗口天数和恰好等于 x 时，直接记录当前金币总和；如果小于 x，则计算剩余天数并用 sumup() 方法加上右侧不足的金币数。

5. 更新最优解：每次计算得到的总金币数与当前的最优解比较，保留最大值。

代码解释

1. get(int n) 函数：计算从 1 到 n 的金币数量，这里使用了高效的数学公式。

2. 主函数逻辑：

   • 输入 n 和 x，以及每个月的天数，并创建一个长度为 2n 的数组。
   • 使用滑动窗口遍历双倍数组，每次更新当前窗口的天数和金币总数。
   • 通过动态调整窗口的左侧，确保总天数不超过 x。
   • 计算当前窗口的金币总数，并实时更新最大金币数量 res。

时间复杂度

该算法的时间复杂度为 (O(n))，每个元素最多被访问两次，因此可以在线性时间内找到答案。

代码实现

C++代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 400010;  // 2倍日历数组的最大长度
typedef long long LL;

// 计算从1到n的和，用于金币数量计算
LL get(int n) {
    return (1ll + n) * n / 2;  // 使用公式计算1到n的和
}

int main() {
    LL n, x;
    cin >> n >> x;  // 输入月数和连续登录天数
    
    // 定义2倍长度数组，并输入日历数据
    LL a[N * 2];  // 双倍长度的数组
    for(int i = 0; i < n; i++) {
       cin >> a[i];  // 输入每个月的天数
       a[i + n] = a[i]; // 复制一份，形成双倍数组
    }

    LL s = 0;  // 当前窗口的总天数
    LL res = 0;  // 最优解，最大金币数
    LL t = 0;  // 当前窗口的金币总数

    // 滑动窗口遍历数组
    for(int i = 0, j = 0; i < 2 * n; ++i) {
        s += a[i];  // 更新当前窗口的天数和
        t += get(a[i]);  // 计算当前天数的金币数量并累加到总金币数
        
        // 动态调整窗口，保持总天数不超过x
        while (s - a[j] >= x) {
            s -= a[j];  // 从窗口左侧移除天数
            t -= get(a[j++]);  // 移除相应的金币数量
        }

        // 计算当前窗口金币数并更新最优解
        res = max(res, t - get(s - x));  // 如果窗口的天数小于x，计算缺失部分金币并更新结果
    }
    
    cout << res << endl;  // 输出最大金币数
    return 0;
}

Python代码

# 计算从 l 到 r 的连续整数和
def sumup(l, r):
    return r * (r + 1) // 2 - l * (l - 1) // 2

# 输入日历长度和连续天数
n, x = map(int, input().split())
d = list(map(int, input().split()))
d += d  # 复制日历数据以处理跨年情况

ans = 0  # 初始化答案为0
cursum = 0  # 当前窗口天数和
cur = 0  # 当前窗口金币总数
l = 0  # 左窗口边界

# 滑动窗口遍历
for i in range(n * 2):
    cursum += d[i]
    cur += d[i] * (d[i] + 1) // 2

    # 若窗口天数和超过 x ，从左边界移除
    while cursum > x:
        cursum -= d[l]
        cur -= d[l] * (d[l] + 1) // 2
        l += 1

    # 计算当前窗口金币数并更新最优解
    curans = cur
    cnt = x - cursum
    if l > 0:
        curans += sumup(d[l - 1] - cnt + 1, d[l - 1])
    ans = max(ans, curans)

print(ans)

Java代码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        long x = scanner.nextLong();
        long[] d = new long[2 * n];

        // 读取日历数据并复制一份
        for (int i = 0; i < n; i++) {
            d[i] = scanner.nextLong();
            d[i + n] = d[i];
        }

        long dayCnt = 0;  // 当前窗口的总天数
        long coinSum = 0;  // 当前窗口金币总数
        int j = 0;  // 左窗口边界
        long ans = 0;  // 最大金币数

        // 滑动窗口遍历日历数组
        for (int i = 0; i < 2 * n; i++) {
            dayCnt += d[i];
            coinSum += d[i] * (1 + d[i]) / 2;

            // 动态调整窗口大小
            while (dayCnt > x) {
                dayCnt -= d[j];
                coinSum -= d[j] * (1 + d[j]) / 2;
                j++;
            }

            // 计算当前窗口金币数并更新最优解
            long rest = x - dayCnt;
            long curans = coinSum;
            if (j > 0) {
                curans += sumup(d[j - 1] - rest + 1, d[j - 1]);
            }
            ans = Math.max(ans, curans);
        }

        System.out.println(ans);
    }

    // 计算从 l 到 r 的和，用于补全天数
    public static long sumup(long l, long r) {
        return r * (r + 1) / 2 - l * (l - 1) / 2;
    }
}

代码注释说明

• 滑动窗口和范围控制：窗口控制中，dayCnt 记录窗口中连续天数之和，若超过 x 天，则缩小左边界。
• 金币计算：每个元素 d[i] 对应的金币数为连续整数的和，可以通过公式 d[i] * (1 + d[i]) / 2 计算。
• 剩余天数计算：若窗口天数和小于 x，则调用 sumup() 计算剩余金币，以补全连续天数，使总天数等于 x。
• 最终输出：输出记录的最大金币数。