题解 | 相邻的糖果

#include<bits/stdc++.h>
#define endl "\n"
#define int long long
using namespace std;
void slove() {
    int n, m, x;
    std::cin >> n >> m >> x;
    std::vector<int> a(n + 2), fa(n + 1);
    for (int i = 1; i <= n; i++) std::cin >> a[i], fa[i] = i;
    auto find = [&](auto&& find, int x)->int{
        return fa[x] == x ? x : fa[x] = find(find, fa[x]);
    };
    if (m >= n) {
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            ans += a[i];
        }
        if (ans > x) ans -= x;
        std::cout << ans << endl;
    } else {
        int ed = m;
        int l = 1;
        int r = m;
        int cur = 0;
        int ans = 0;
        for (int i = l; i <= r; i++) cur += a[i];
        while (r <= n) {
            ed = r;
            while (ed >= 1 && cur > x) {
                int need = cur - x;
                if (need >= a[ed]) {
                    cur -= a[ed];
                    need -= a[ed];
                    ans += a[ed];
                    a[ed] = 0;
                    fa[find(find, ed)] = find(find, ed - 1);
                    ed = find(find, ed - 1);
                } else {
                    ans += need;
                    a[ed] -= need;
                    cur -= need;
                    break;
                }
            }
            r++;
            if (r <= n)cur += a[r];
            if (l <= n)cur -= a[l];
            l++;
            //std::cout<<ans<<endl;
        }
        std::cout << ans << endl;
    }
}
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int T = 1;
    //std::cin>>T;
    while (T--)    {
        slove();
    }
    return 0;
}