题解 | 贪心思路

如果把每组m个元素看成一个分区，我们的分区示意图如下：

可以明显看到：每个m元素的分区，削减最后一个元素，可以让影响后续m个分区，使它们的负担变小，因此我们的贪心策略是：每次优先删除一个分区的最后几个元素，因为这样可以帮助后续几个分区的总和一起减小。

在实现上，维护一个变量s，用来表示当前窗口的值，每次需要删除时，直接暴力枚举，也能过。

因为每个区间的操作次数与k其实是正相关的，比方说，假设k非常小，但区间和很大，那第一个区间处理完后，第二个区间就几乎不需要怎么处理，理论上的时间复杂度是的，但由于这个贪心思路，使得每次删除都使得不合法区间数量收敛的特别快

如果区间很小，那就代表m很小，每次暴力枚举的次数也少，时间复杂度接近。

如果区间很大，极端情况下是x很小，但区间大的话，如果删除一个区间的最后一个元素，会产生的反应，具体证明应该是计算整个数组最多一共需要减多少，然后再计算每次删一个元素，平均能减多少，这样下来几乎能过。

不太懂这些，还望有大佬证明证明

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+7;
typedef long long ll;
int n,m,x;
ll a[N];
//优先删每个分组最后的
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    cin>>n>>m>>x;
    m=min(n,m);
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    ll s=0;
    ll ans=0;
    for(int i=1;i<=n;i++){ //枚举每个分组最后一个
        s+=a[i];
        if(i>=m && s>x){
            ll need=s-x;
            for(int j=i;j>=i-m+1 && need; j--){
                if(need>a[j]){ //如果超出了，就能减多少是多少
                    need-=a[j];
                    s-=a[j];
                    ans+=a[j];
                    a[j]=0;

                }
                else {
                    s-=need;
                    ans+=need;
                    a[j]-=need;
                    need=0;
                }
            }
        }
        if(i>=m)s-=a[i-m+1];
    }
    cout<<ans;
    return 0;
}