题解 P4754 【True Vegetable】

· · 题解

如果一边被减一边填补，因为情况较多，决策难以判断。

如果直接二分时间，因为某个位置的难度可能一时被减去较多，不满足二分性质。

令被减去的时间为时间点，考虑二分被减的时间点，然后将难度先减去要减的值，因为减难度的冷却时间不小于需要加的数量，被减的数量可以用相同数量的时间填补，所以当一个时间点可以达到目标时，下一个时间点必然也能达到目标。

然后在时间点上计算出需要的时间。二分时间点，在减去生效的操作后，我们可以贪心地从左到右地考虑，当位置 i 小于 1 时，考虑贪心地将 [i,i+K-1] 这个区间加 1，可以使需要的回合数尽量小。当确定小B有哪些操作生效时，这样就可以求出满足条件的准确最小时间，若这个时间小于下个时间点，那么check()就是有效的。

时间复杂度 O(N\ log\ N)

#include <bits/stdc++.h>
#define ll long long
#define MAXN 500205
#define INF 2147483647
using namespace std;
struct sth
{
    int w,t;
    sth(){}
    sth(int n1,int n2){w=n1,t=n2;}
}q[MAXN];
    int n,m,k,l,ans;
    int a[MAXN],w[MAXN],x[MAXN],v[MAXN],r[MAXN],b[MAXN],d[MAXN];
int inline read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int cal(int x)
{
    memcpy(b,a,sizeof(a));
    memset(d,0,sizeof(d));
    for (int i=1;i<=x;i++)
        b[::x[i]]-=v[i];
    int tmp=0,step=0,dis;
    for (int i=1;i<=n;i++)
    {
        if (b[i]+tmp<=1)
        {
            dis=1-b[i]-tmp;
            step+=dis;
            d[i]+=dis;
            if (i+k-1<=n)
                d[i+k-1]-=dis;
        }
        tmp+=d[i];
    }
    return max(w[x],step);
}
int main()
{
    n=read(),m=read(),k=read(),l=read();
    for (int i=1;i<=n;i++)
        a[i]=read();
    for (int i=1;i<=l;i++)
        r[i]=read();
    for (int i=1;i<=m;i++)
        w[i]=read(),x[i]=read(),v[i]=read();
    w[0]=0,w[m+1]=INF;
    int le=0,ri=m,mid;
    while (le<=ri)
    {
        mid=le+ri>>1;
        if (cal(mid)<w[mid+1]) ans=mid,ri=mid-1;
        else le=mid+1;
    }
    printf("%d\n",cal(ans));
    return 0;
}