260720贪心I ARC220C

许卿安 · 2026-07-21 21:33:25 · 题解

反悔贪心。

我们要贪心地使前面的数变成 0。当从前往后考虑到第 i 个位置时，假设覆盖 i-1 的区间有 f 个，我们先将这 f 个区间延长到 i。此时 i 位置的值为 (a_i+f)\bmod m，记为 d。为了让其变成 0，我们有以下两种决策：

• 若 f\ge d，则可以使 d 个区间在 i-1 结束，只保留 f-d 个区间。此时 i 位置的值为 (a_i+f-d)\bmod m=0。
• 还可以在 i 处新开 m-d 个区间。此时 i 位置的值为 (a_i+f+m-d)\bmod m=0。

由于关掉区间不需要花费，所以我们优先关区间。但是，如此我们无法再将这 d 个区间向后延申，可能并不是最优的方案。于是我们将 m-d 放入一个小根堆，方便后面反悔。

当 f<d 时，我们只能选择决策二。此时我们选出小根堆中最小的 m-d，记为 tp。

• 如果剩余 k<tp，则我们无论如何都不能使 a_i=0。此时将小根堆和 f 清空即可。
• 否则，我们将该处的决策由一改为二。这样我们就可以用 tp 的代价使 f 增加 m，此时的 f 就足够减去 d 了。

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N=3e5+2;
int a[N];
priority_queue<int,vector<int>,greater<int>> pq;

signed main(){
    int t;cin>>t;
    while(t--){
        while(!pq.empty()) pq.pop();
        int n,m,k;cin>>n>>m>>k;
        for(int i=1; i<=n; i++) cin>>a[i];
        int f=0;
        for(int i=1; i<=n; i++){
            int d=(a[i]+f)%m;
            pq.push(m-d);
            if(f<d){
                int tp=pq.top();pq.pop();
                if(k<tp){
                    f=0;
                    while(!pq.empty()) pq.pop();
                }
                else k-=tp,f+=m-d,a[i]=0;
            }
            else f-=d,a[i]=0;
        }
        for(int i=1; i<=n; i++) cout<<a[i]<<" \n"[i==n];
    }
    return 0;
}