P14576 Lamborghini (Remix) 题解

· · 题解

1. 题意解释

给出一段 n 行的代码，每行的长度为 a_i，你可以在某些行的末尾处放上光标，并使所有光标移动任意次，求一行上最多可以有多少个光标。

2. 思路

可以知道这一行的光标编号一定是连续的，且不论怎么移动，光标间的距离是保持不变的。

因此我们可以预处理光标距离的前缀和，以做到 O(1) 查询两个光标间的距离。

然后我们发现答案是有单调性的，考虑二分答案。

考虑对于光标数量 x 如何判断正确性。

枚举第一个光标的编号 i，则这一串光标的总长度即为 sum_{i+x-1}-sum_i。

如果代码中有一行的长度大于等于光标总长度，那么我们总可以通过移动把这一串光标移到这一行。

所以我们只需要判断 sum_{i+x-1}-sum_i 是否小于等于最长代码行的长度就可以了。

有一些细节见代码注释。

3. 代码实现

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,a[200200],sum[200200],ans,maxn;
bool check(int x){
    for(int i=1;i+x-1<=n;i++){
        int l=sum[i+x-1]-sum[i];//注意第 i 个光标的距离是不算在内的，所以这里是 sum[i] 而不是 sum[i-1]
        if(l<=maxn){
            return true;
        }
    }
    return false;
}
signed main(){
    cin>>t;
    while(t--){
        cin>>n;
        sum[0]=0;
        maxn=-1e9;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            a[i]++;//光标从当前行移动到下一行还要一次移动，所以相当于代码行长度加一
            sum[i]=sum[i-1]+a[i];
            maxn=max(maxn,a[i]-1);
        }
        int l=1,r=n;
        while(l<=r){
            int mid=(l+r)>>1;
            if(check(mid)){
                ans=mid;
                l=mid+1;
            }
            else{
                r=mid-1;
            }
        }
        cout<<ans<<'\n';
    }
    return 0;
}