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

· · 题解

[集训队互测 2023] 优惠购物

​ 题目大意是给定 n,m,c 表示总共有 n 个商品，初始时有 m 张优惠卷，和一个参数，每个商品有 a_i,b_i，依次考虑每一个商品，你可以考虑使用 x(0\leq x\leq b_i) 张优惠卷，然后购买这个商品的价格就是 a_i-x，购买完之后获得 \lfloor \frac {a_i-x} c\rfloor 张优惠卷，问最少花多少钱能拿下所有的商品。n\leq 10^6,m,c\leq 10^9。

​ 考虑直接啥也不用，大手一挥，全款拿下所有商品，然后此时再考虑在哪里使用优惠卷是最优的，我们记一个位置使用了 x_i 个优惠卷。

​ 首先第一部分肯定是使用 x_i= (a_i\bmod c) 张优惠卷，因为这样子发现获得的优惠卷数量是不变的，所以尽可能先这么用。

​ 那这个策略可以直接从前往后扫，记录当前还剩多少个优惠卷，尽可能的使用就好了。

​ 然后再考虑第二阶段，这个时候你的选择应该是花 c 的倍数张优惠卷，因为这样子你每花 c 张获得的才减少 1，肯定是优于你花 <c 张获得的就少一张的。

​ 于是这一段你考虑怎么怎么贪心的取，因为获得的优惠卷会减少，所以你尽可能地在后面去选，也就是从后往前枚举，记一个 s_i 表示购买完前 i 个物品之后拥有多少优惠卷，那这一个位置可以花的优惠卷就会受到如下限制：他最最多可以花 \min(\frac{b_i-x_i} c,\frac{s_{i-1}-x_i} c,\frac{\min_{j>i} s_{j-1}-x_j}{c+1}) 张优惠卷，分别是自身的使用数量上限，前面还留下了多少的限制，以及对后面影响的限制，于是你倒着扫，动态维护一下后缀 \min 即可，这部分也是 O(n) 的。

​ 然后在考虑如果还有剩的第三部分，这时候我们要花一个物体上 <c 张优惠卷，那么显然花 c-1 张肯定是比花 c-2 张更优的，所以我们考虑还是每次找到一个最靠后的位置，使得他能花最多的优惠卷。

​ 那么一个位置能花的优惠卷就是 \min(b_i-x_i,s_{i-1}-x_i,\min_{j>i}s_{j-1}-x_j-1) 显然除了 b_i-x_i 后面的两项取 \min 是随着 i 增递减的，那么我们考虑手动让 b_i-x_i 有单调性，于是按照 b_i-x_i 排序，然后从大往小加入，每一次把所有相同的值加进去，然后找到现在在集合里最大的位置，考察它的 \min(s_i-1-x_i,\min_{j>i}s_{j-1}-x_j-1) 是否大于等于当前枚举的 b_i-x_i 是的话那就可以知道他要多花当前枚举 b_i-x_i 张优惠卷，显然这会对后面能使用的优惠卷数量造成影响，用线段树后缀加即可，前面的那个 \min 值也只需要线段树后缀 \min，取出最大的位置使用堆即可，这部分时间复杂度 O(n\log n)。 ::::success[Code]

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
#define ll long long 
int n,m,c,a[N],b[N],us[N],id[N];
ll s[N];
struct tree{
    int lz;
    ll minn;
}tr[N<<2];
inline void pushup(int x){ tr[x].minn=min(tr[x<<1].minn,tr[x<<1|1].minn); }
inline void pushtag(int x,int val){ tr[x].minn+=val,tr[x].lz+=val; }
inline void pushdown(int x){ pushtag(x<<1,tr[x].lz),pushtag(x<<1|1,tr[x].lz),tr[x].lz=0; }
void build(int x,int l,int r){
    tr[x].lz=0;
    if(l==r){
        tr[x].minn=s[l-1]-us[l];
        return;
    }
    int mid=(l+r)>>1;
    build(x<<1,l,mid),build(x<<1|1,mid+1,r);
    pushup(x);
}
void change(int x,int l,int r,int ml,int mr,int val){
    if(ml>mr) return;
    if(ml<=l&&r<=mr){
        pushtag(x,val);
        return;
    }
    pushdown(x);
    int mid=(l+r)>>1;
    if(ml<=mid) change(x<<1,l,mid,ml,mr,val);
    if(mid+1<=mr) change(x<<1|1,mid+1,r,ml,mr,val);
    pushup(x);
}
ll ask(int x,int l,int r,int ml,int mr){
    if(ml>mr) return 1e18;
    if(ml<=l&&r<=mr) return tr[x].minn;
    pushdown(x);
    int mid=(l+r)>>1;
    ll ret=1e18;
    if(ml<=mid) ret=min(ret,ask(x<<1,l,mid,ml,mr));
    if(mid+1<=mr) ret=min(ret,ask(x<<1|1,mid+1,r,ml,mr));
    return ret;
}
bool cmp(int x,int y){ return b[x]-us[x]<b[y]-us[y]; }
void work(){
    scanf("%d%d%d",&n,&m,&c);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),us[i]=s[i]=0;
    for(int i=1;i<=n;i++) scanf("%d",&b[i]);
    s[0]=m;
    for(int i=1;i<=n;i++){
        int val=min({(ll)a[i]%c,(ll)b[i],s[i-1]});
        us[i]=val,s[i]=s[i-1]-val+(a[i]-val)/c;
    }
    ll minn=1e18;
    for(int i=n;i>=1;i--){
        int cnt=min({(ll)(s[i-1]-us[i])/c,(ll)(b[i]-us[i])/c,minn});
        us[i]=us[i]+1ll*cnt*c;
        minn=min(minn-cnt,(s[i-1]-us[i])/(c+1));
    }
    for(int i=1;i<=n;i++) s[i]=s[i-1]-us[i]+(a[i]-us[i])/c;
    build(1,1,n);
    priority_queue<int> pos;
    for(int i=1;i<=n;i++) id[i]=i;
    sort(id+1,id+n+1,cmp);
    int tot=n;
    while(tot){
        int Tot=tot;
        while(Tot&&b[id[Tot]]-us[id[Tot]]==b[id[tot]]-us[id[tot]]) pos.push(id[Tot]),Tot--;
        int lim=b[id[Tot]]-us[id[Tot]];
        while(!pos.empty()){
            int x=pos.top();
            int Lim=min(ask(1,1,n,x,x),ask(1,1,n,x+1,n)-1);
            if(Lim<=lim) break;
            int val=min(b[x]-us[x],Lim);
            us[x]+=val,change(1,1,n,x,x,-val),change(1,1,n,x+1,n,-val-1);
            pos.pop();
        }
        tot=Tot;
    }
    ll ans=0;
    for(int i=1;i<=n;i++) ans+=a[i]-us[i];
    printf("%lld\n",ans);
}
int main(){
    int _;
    scanf("%d",&_);
    while(_--) work();
}

::::