题解：P10001 [集训队互测 2023] 优惠购物

· · 题解

QOJ 最短解第一页。

最大化使用的券个数，策略形如攒券然后集体花掉。

笔者一开始的想法是通过调整法证明，用券个数在 (0,b) 的物品至多一个，假设存在 i<j 都用了 (0,b)，将 i 处用的券提后到 j 用，并认为总钱数不会增大。但是这是错的，因为会产生除以 c 取整问题。

因为是每 c 个换一张券，所以调整时可以集体调整 c 个券，将 i 的券提后到 j 用，这样还能在 j 处多一张券。

从前往后买时，是否节省券是未知的，因此考虑反悔贪心，维护每个前缀的最优解，并动态进行调整。

假设我们已经确定了 1\sim i-1 每个物品的实际花费 y_i，剩余了 T 张券，处理物品 a_i,b_i 时，默认 i 是最后一个元素，并希望在 [1,i] 已使用券最多的前提下，留给 [i+1,n] 的券最多。

令 y_i=a_i-b_i，记 d_i=c-(y_i\bmod c)，设当前有 T 个剩余券，当 a_i-y_i-T\geq \min_{j<i} d_j 时，可以增加 [1,i] 使用的券个数，将 y_j\gets y_j+d_j，多出来的 d_j+1 张券给 i。否则不能增加前缀用券数，若 a_i-y_i>T，不断选 [1,i] 中 d 最小的位置令其 y 加一，直到能以 y_i 价格买下物品 i。特别地，需要特判不能把 y 加过对应的 a，若 y+d>a 需要把 d 设为 +\infin。

使用堆优化此过程，存储 (d_i,i) 对，当 y=a 时移除此元素。堆内每个元素被访问后，要么切换当前的分讨状态，要么被移除，复杂度 O(n\log n)。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll inf=1e18;
int n;
ll m,c,a[1000005],b[1000005],y[1000005],d[1000005];
priority_queue<pair<ll,int>> Q;
void Inq(int i){
    d[i]=c-(y[i]%c);
    if(y[i]+d[i]>a[i]) d[i]=inf;
    if(y[i]<a[i]) Q.push({-d[i],i});
}
void solve(){
    cin>>n>>m>>c;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    ll T=m;
    for(int i=1;i<=n;i++){
        y[i]=a[i]-b[i];
        while(!Q.empty()&&a[i]-y[i]-T>=-Q.top().first){
            int j=Q.top().second;Q.pop();
            if(d[j]==c){
                ll k=max(min((a[i]-y[i]-T)/(c+1),(a[j]-y[j])/c),1ll);
                y[j]+=c*k,T+=(c+1)*k;
            }else y[j]+=d[j],T+=d[j]+1;
            Inq(j);
        }
        Inq(i);
        while(!Q.empty()&&T<a[i]-y[i]){
            int j=Q.top().second;Q.pop();
            if(j==i){
                if(d[i]>=c) y[i]=a[i]-T;
                else y[i]=min(y[i]+d[i],a[i]-T);
                Inq(i);
            }else{
                ll cnt=a[i]-y[i]-T;
                y[j]+=cnt,T+=cnt;
                Inq(j);
            }
        }
        T-=(a[i]-y[i]);
        T+=(y[i]/c);
    }
    while(!Q.empty()) Q.pop();
    ll res=0;
    for(int i=1;i<=n;i++) res+=y[i];
    cout<<res<<"\n";
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}