Problem Link

题目大意

给定 $n$ 个物品，你要按顺序购买每个物品，初始有 $m$ 个优惠券。

对于第 $i$ 个物品，你要花费总计 $a_i$ 个金币或优惠券，其中优惠券至多用 $b_i$ 张，并且你每付出 $c$ 个金币就会获得一张优惠券（向下取整）。

最小化花费的金币总数。

数据范围：$n\le 10^6$。

思路分析

假设第 $i$ 次购买时花费了 $x_i$ 张优惠券，那么前 $i$ 次操作后剩余的优惠券 $s_i=m+\sum\limits_{j=1}^i \left\lfloor\dfrac{a_j-x_j}c\right\rfloor-x_j$，唯一的限制就是 $\forall i\in[1,n+1]:x_i\le s_{i-1}$。

考虑如何贪心解决这个问题。

我们分析优惠券从 $0$ 开始不断增加的过程：

• 使用的前 $a_i\bmod c$ 张优惠券：使用任意多张都不会减少获得的优惠券，因此贪心使用尽可能多的这种优惠券。
• 接下来每使用 $c$ 张优惠券，都会使得后续剩余优惠券数量额外 $-1$。
• 对于剩余的最后 $<c$ 张优惠券，还会使得后续剩余优惠券数量 $-1$。

容易发现所有的操作中，第一种操作显然最优，然后是第二种和第三种。

那么我们先进行所有的第一种操作，容易发现在哪个位置操作仅仅相当于改变 $m$，无后效性，因此可以随意操作，不妨从前往后依次取，即 $x_i=\min(a_i\bmod c,b_i,s_{i-1})$。

然后我们要进行一些第二种操作，即在某个位置连续使用 $c$ 张优惠券。

我们发现这种情况下收益相同，使用的位置显然越靠后后效性越小，因此从后往前贪心取尽可能多的 $x_i$ 即可。

那么此时第 $i$ 个位置会使用 $\min\left(\left\lfloor\dfrac{b_i-x_i}c\right\rfloor,\left\lfloor\dfrac{s_{i-1}-x_i}c\right\rfloor,\min\limits_{i<j\le n+1}\left\lfloor\dfrac{s_{j-1}-x_j}{c+1}\right\rfloor\right)$ 轮 $c$ 张优惠券。

最后第三种情况，我们只要考虑每个点剩余使用的优惠券数 $\in[0,c)$ 的剩余情况。

根据贪心，我们依然要优先做收益最高的操作，即可以使用优惠券数最多的操作。

记 $t_i=s_{i-1}-x_i$ 在第 $i$ 个位置最多可以使用的优惠券数量就是 $\min(b_i-x_i,t_i,\min_{i<j\le n+1}t_j-1)$。

观察这个结构的性质，我们发现 $d_i=\min(t_i,\min _{i<j\le n+1} t_j-1)$ 具有单调性，随着 $i$ 的增加而递增，而且在整个贪心过程中其单调性始终存在。

那么考虑模拟这个过程，我们从大往小枚举 $w=c-1\sim 0$，求出 $\min(d_i,b_i-x_i)=w$ 的所有位置然后操作。

考虑如何维护这些位置，首先这些位置显然满足 $b_i-x_i\ge w$，而 $b_i-x_i$ 是定值，因此可以离线，在 $w=b_i-x_i$ 时插入操作 $i$，那么我们只要取出所有 $d_i\ge w$ 的操作即可。

而 $d_i$ 从后往前递减，因此 $d_i\ge w$ 的 $i$ 一定是 $1\sim n$ 的一段后缀，用堆维护所有被插入的操作 $i$ 中的最大值，判断是否有 $d_i\ge w$ 即可。

容易发现我们只要处理等于某个 $b_i-x_i$ 的所有 $w$，中间的 $w$ 不需要考虑，只要大于下一个 $b_i-x_i$ 的所有 $d_i$ 都操作即可。

我们可以用线段树动态维护 $d_i$，只要区间加区间最小值即可。

时间复杂度 $\mathcal O(n\log n)$。

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e6+5;
int n,id[MAXN];
ll c,a[MAXN],b[MAXN],s[MAXN],x[MAXN],up[MAXN];
struct SegmentTree {
	ll tr[MAXN<<2],tg[MAXN<<2];
	void psu(int p) { tr[p]=min(tr[p<<1],tr[p<<1|1]); }
	void adt(int p,int k) { tr[p]+=k,tg[p]+=k; }
	void psd(int p) { adt(p<<1,tg[p]),adt(p<<1|1,tg[p]),tg[p]=0; }
	void init(int l=1,int r=n+1,int p=1) {
		tr[p]=tg[p]=0;
		if(l==r) return tr[p]=s[l-1]-x[l],void();
		int mid=(l+r)>>1;
		init(l,mid,p<<1),init(mid+1,r,p<<1|1);
		psu(p);
	}
	void add(int ul,int ur,int k,int l=1,int r=n+1,int p=1) {
		if(ul<=l&&r<=ur) return adt(p,k);
		int mid=(l+r)>>1; psd(p);
		if(ul<=mid) add(ul,ur,k,l,mid,p<<1);
		if(mid<ur) add(ul,ur,k,mid+1,r,p<<1|1);
		psu(p);
	}
	ll qry(int ul,int ur,int l=1,int r=n+1,int p=1) {
		if(ul<=l&&r<=ur) return tr[p];
		int mid=(l+r)>>1; psd(p);
		if(ur<=mid) return qry(ul,ur,l,mid,p<<1);
		if(mid<ul) return qry(ul,ur,mid+1,r,p<<1|1);
		return min(qry(ul,ur,l,mid,p<<1),qry(ul,ur,mid+1,r,p<<1|1));
	}
}	T;
void solve() {
	scanf("%d%lld%lld",&n,&s[0],&c);
	for(int i=1;i<=n;++i) scanf("%lld",&a[i]);
	for(int i=1;i<=n;++i) scanf("%lld",&b[i]);
	for(int i=1;i<=n;++i) {
		ll w=min({a[i]%c,b[i],s[i-1]});
		x[i]=w,s[i]=s[i-1]-x[i]+(a[i]-x[i])/c;
	}
	ll lim=s[n];
	for(int i=n;i>=1;--i) {
		ll w=min({(b[i]-x[i])/c,(s[i-1]-x[i])/c,lim/(c+1)});
		x[i]+=c*w,lim=min(lim-(c+1)*w,s[i-1]-x[i]);
	}
	for(int i=1;i<=n;++i) s[i]=s[i-1]-x[i]+(a[i]-x[i])/c;
	x[n+1]=id[n+1]=0,T.init();
	for(int i=1;i<=n;++i) id[i]=i,up[i]=min(c-1,b[i]-x[i]);
	sort(id+1,id+n+1,[&](int i,int j){ return up[i]>up[j]; });
	priority_queue <int> Q;
	for(int i=1,j;i<=n;i=j) {
		for(j=i;j<=n&&up[id[j]]==up[id[i]];++j) Q.push(id[j]);
		while(Q.size()) {
			int u=Q.top();
			ll z=min({up[u],T.qry(u,u),T.qry(u+1,n+1)-1});
			if(z>up[id[j]]) {
				Q.pop(),x[u]+=z,T.add(u,u,-z),T.add(u+1,n+1,-z-1);
			} else break;
		}
	}
	ll ans=0;
	for(int i=1;i<=n;++i) ans+=a[i]-x[i];
	printf("%lld\n",ans);
}
signed main() {
	int o; scanf("%d",&o);
	while(o--) solve();
	return 0;
}