Ps:

1.含有一版代码

2. 包含本人做题思路（包括错误思路总结）-> 专放于“做题思路”一节

3. sum (窗口数据求和）、num[ ]（储存输入元素）、n（元素总个数）、x（限定最大值）、m（窗口长度/相邻盒子数）、ans（答案）

一。思路

1. 分析题意：

（1）数据范围：n, m, x(2 ≤ n,m ≤ 106,1 ≤ x ≤ 109) -> 时间复杂度只能是O(n)及以下，元素用long long类型（长整型）

（2）题意理解（约束条件）：A. m个相邻的盒子 -> 窗口； B.最少操作次数 -> 求数据量； C.任何m个相邻的盒子内糖果数量不能超过x个 -> 窗口内的值的sum不超过x

2.理解：

（1）如何存数据？

可以用数组num[ ] 来存储元素 ai 

（2）如何计算？

不难发现，我们移动窗口时，sum的变化只与num[ i ] 和 num [ i+m ] 有关，即每移动一次，会发生：A. sum - num [ i ] ； B. sum + num[ i + m ] （注意顺序，这个很关键）。我们又知道，ans一定是所有溢出的和。可见，ans和 num[ i ]、num[ i+m ]有关。仔细思考一下，你就能找到盲点：A. num[ i ] 的值在开始（i== 0）时，只能影响第一个 窗口（贡献1），而num[ i+m ] 可以影响m+1个窗口（贡献m+1）； B. 当改变一个元素时，能影响的窗口越多，就能 改变越少的元素达到效果。 所以，我们只需要每次顺序计算标蓝的式子，就可以算出答案啦！（仔细想想，这个是 本题的关键-> 贪心）。

（3）细节：

A. 每次修改都要修改原元素（因为还要用）

B. 修改顺序不要错

（4）优化：

A. 直接在输入时进行运算

B. 用c的输入方式降低输入所耗时间

二。完整代码：

#include<iostream>
using namespace std;

const int N = 1e6 + 5;
using LL = long long;    // 等价于 typedef long long LL;
LL num[N];

int main() {
    LL n, m, x;        // 可用int
    cin >> n >> m >> x;
    LL sum = 0, ans = 0;
    for (int i = 0; i < n; i++) {
        int j = i - m;      //窗口[left,right],这里计算left（下标）
        cin >> num[i];
        if (j >= 0) {       //如果left>=0,即窗口已经完全划入，减掉left的值（对应A操作）
            sum -= num[j];
        }
        if (sum + num[i] > x) {  //如果超过，ans加上超出部分，num[i]保留剩下部分）
            ans += sum + num[i] - x;
            num[i] = x - sum;
            sum = x;
        }
        else sum += num[i];      //如果没超，sum加上right的值

    }

    cout << ans;

    return 0;
}

三。思想总结

我相信，大家都能考虑到left和right这一步，但是不明白为啥贪心。我一开始也不明白，但是想了想，能发现：窗口和遍历数组都不可避免，所以我们只有将修改的次数降低，修改的贡献提高（一次修改对m+1个窗口有效），才能找到答案（假设ans为答案，cmu为总需要贡献，一个元素平均贡献为w，可以知道：ans ~ cmu / w。所以w越大，ans越小，就越靠近答案，这就和贪心联系上了<每次找贡献最大的元素更新>) 。

四。我的错误总结

其实没啥可说的，我的错误点都在前面讲透了，唯一注意的是 += 不要写成 = ，我因为这个卡了好久。其次就是，注意题目数据范围，思考解题的方法，毕竟1e6的数据量不可能用两层for循环。

最后的最后，感谢阅读，希望帮到你！