P14576 题解

显然在每行后面都放一个光标一定不劣。接下来先考虑光标向左移动的情况，那么处在同一行的光标一定是若干个连续行末的光标，为了让它们同行的机会尽可能多，应该在它们前面最长的一行来实现。考虑枚举区间左端点，同时记录前缀最大值，那么显然可以直接二分最远的右端点，要求这两个光标距离不能超过前缀最大值，然后更新答案即可。时间复杂度

O(Tn\log n)

。

CPP

#include<iostream>
#include<cstdio>
#define int long long
using namespace std;
#define N 1000010
int n,a[N],sum[N],mx,ans;
void solve(){
    ans=0;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
        sum[i]=sum[i-1]+a[i]+(i>1);
    mx=0;//按左
    for(int i=1;i<=n;i++){
        mx=max(mx,a[i]);
        int l=i,r=n,mid,pp=i;
        while(l<=r){
            mid=(l+r)/2;
            if(sum[mid]-sum[i]<=mx)pp=mid,l=mid+1;
            else r=mid-1;
        }
        ans=max(ans,pp-i+1);
    }
    for(int i=1;i<=n;i++)
        sum[i]=sum[i-1]+a[i]+(i<n);
    mx=0;//按右
    for(int i=n;i>=1;i--){
        int l=1,r=i,mid,pp=i;
        while(l<=r){
            mid=(l+r)/2;
            if(sum[i]-sum[mid]<=mx)pp=mid,r=mid-1;
            else l=mid+1;
        }
        ans=max(ans,i-pp+1);
        mx=max(mx,a[i]);
    }
    cout<<ans<<'\n';
    return;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int T;
    cin>>T;
    while(T--)
        solve();
    return 0;
}

文章操作

相关推荐

评论

P14576 题解