2022 ICPC NJ D

D. Chat Program

二分答案x
我们考虑如何O（n）check
首先我们可以将大于等于x的都看成1 否则看成0
题意转化为我们通过一次操作将这个01序列中的1变得大于k个
我们设dp[i]为i为长度m的等差数列的尾巴能改变多少个0->1
对于每个a[i]我们可以O（1）搞出他对dp[i]的一个区间+1
然后我们扫一遍即可
最后注意我们m有2e5个 ai是1e9 所以二分最大为2e14
还有就是一些细节比如 我们

前面m个的话最多只能+ c+d*min(i-1,m-1) 而不是等差数列最大的那项

int a[200010],n,k,m,c,d,f[200010];//f[i]表示i是头有多少可以变成1
vector<int>s;
bool check(int x){
    int cnt = 0;
    for (int i = 1; i <= n; i++) cnt += a[i] >= x ? 1 : 0;
    if (cnt >= k) return true;
    for(int i=0;i<=n+3;i++)f[i]=0;
    for(int i=1;i<=n;i++){
        if(a[i]>=x||a[i]+c+d*min(i-1,m-1)<x)continue;
        f[max(m,i)]++;
        auto it=lower_bound(all(s),x-a[i]);
        f[min(n+1,i+m-(it-s.begin()))]--;
    }
    for(int i=1;i<=n;i++)f[i]+=f[i-1];
    for(int i=m;i<=n;i++){
        if(f[i]>=k-cnt)return true;
    }
    return false;
}
void solve(){
    cin>>n>>k>>m>>c>>d;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=m;i++){
        if(i==1)s.push_back(c);
        else s.push_back(s.back()+d);
    }
    int l=0,r=1e15;
    while(l<r){
        int mid=l+r+1>>1;
        if(check(mid))l=mid;
        else r=mid-1;
    }
    cout<<l<<endl;
}

原文地址：https://www.cnblogs.com/ycllz/p/17047702.html