自动搬运

查看原文

来自洛谷，原作者为

	mRXxy0o0 风轻抚过琴弦，也吹乱一时思绪

搬运于2025-08-24 22:36:34，当前版本为作者最后更新于2024-10-29 19:26:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一种比较无脑的做法。

分析

首先考虑二分答案 $mid$，然后对于每一种灌木，算出至少要减的次数 $b_i=\max(0,\lfloor\dfrac{h_i+m\times d_i-mid}x\rfloor)$，不难发现，每个灌木一定恰好减 $b_i$ 次。

对于每次检查答案，直接贪心地操作当天每一个要减且可以减的灌木。这样做法的正确性是明显的，因为先操作总是优于后操作。设二分值域为 $V$，复杂度是 $O(nm\log V)$，会被卡。

于是考虑优化找到一个可减的灌木这一步，维护一个集合存储第 $i$ 天所有可以被修剪的灌木，每修建一个就算出它下一次可以修建的时间，并在对应时间的 vector 中加入这个灌木。于是就做到了 $O(mk\log V)$。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e4+10;
int ne[N];
ll n,m,k,x,h[N],d[N],a[N],tim[N],b[N];
vector<int>G[N],q;
inline bool check(ll mid){
	ll sb=0,ss=0;
	ne[0]=1;
	q.clear();
	for(int i=1;i<=m;++i) G[i].clear();
	for(int i=1;i<=n;++i){
		a[i]=h[i],tim[i]=0,b[i]=max(0ll,(h[i]+d[i]*m-mid+x-1)/x),sb+=b[i],ne[i]=i+1;
		if(!d[i]) ss+=b[i];
		else if(b[i]) G[max(1ll,(x-a[i]+d[i]-1)/d[i])].push_back(i);
	}
	if(sb>m*k) return 0;
	for(int i=1;i<=m;++i){
		if(G[i].size()>q.size()) swap(q,G[i]);
		for(int j:G[i]) q.push_back(j);
		int t=k;
		while(!q.empty()&&t){
			int j=q.back();
			a[j]+=d[j]*(i-tim[j]);
			tim[j]=i;
			while(t&&b[j]&&a[j]>=x) --t,a[j]-=x,--b[j];
			if(b[j]){
				if((x-a[j]+d[j]-1)/d[j]+i<=m) G[max(1ll,(x-a[j]+d[j]-1)/d[j])+i].push_back(j);
				else return 0;
			}
			q.pop_back();
		}
		ss-=t;
	}
	if(ss>0) return 0;
	for(int i=1;i<=n;++i){
		if(!d[i]) continue;
		a[i]+=d[i]*(m-tim[i]);
		if(a[i]>mid) return 0;
	}
	return 1;
}
int main(){
	scanf("%lld%lld%lld%lld",&n,&m,&k,&x);
	ll l=-1ll*m*k*x,r=0,ans;
	for(int i=1;i<=n;++i) scanf("%lld%lld",&h[i],&d[i]),l+=h[i]+d[i]*m,r=max(r,h[i]+d[i]*m);
	l/=n;
	l=max(l,0ll);
	ans=r;
	while(l<=r){
		ll mid=l+r>>1;
		if(check(mid)) r=mid-1,ans=mid;
		else l=mid+1;
	}
	printf("%lld",ans);
	return 0;
}