题解：P8170 [eJOI2021] Waterfront

mRXxy0o0 · 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;
}