本题是一个经典的贪心算法结合滑动窗口的问题。

当发现一个区间 的糖果总和超过 时，我们必须吃掉多余的糖果。 问题在于：应该吃掉区间内哪一个盒子里的糖果？

  • 策略A（吃左边）：如果吃掉区间最左边的糖果（即 ），它只能帮助当前区间满足条件，那个位置马上就会滑出下一个窗口，对后续区间的贡献为0。
  • 策略B（吃右边）：如果吃掉区间最右边的糖果（即 ），它不仅帮助当前区间满足了条件，而且该位置在后续的 个滑动窗口中仍然存在。这意味着这次操作能最大程度地“惠及”后续的窗口，减少未来的操作需求。

结论：根据贪心策略，为了使总操作次数最少，每次必须优先由当前窗口的最右侧元素承担减少糖果的任务。

  1. 维护窗口和：我们维护一个长度为 的滑动窗口的总和 current_sum。
  2. 动态调整：从左向右遍历数组，随着窗口向右滑动，新的元素进入窗口，旧的元素移出窗口。
  3. 贪心修正：在每个位置，如果当前窗口的和大于 ，计算超出部分 diff = current_sum - x。

    • 将 diff 加入总操作数。

    • 从窗口最右侧的盒子中减去 diff 个糖果（这会修改原数组或当前维护的序列值，从而影响后续窗口计算）。

    • 更新 current_sum，使其变为 。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    ll x;
    cin >> n >> m >> x;
    ll sum = 0;
    ll ops = 0;
    vector<ll> a(n);

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        sum += a[i];
        if (i >= m) {
            sum -= a[i - m];
        }
        if (sum > x) {
            ll delta = sum - x;
            ops += delta;
            a[i] -= delta;
            sum = x;
        }
    }

    cout << ops << endl;
}