题解：P14576 Lamborghini (Remix)

zy_oier · 2025-11-23 19:06:09 · 题解

前置知识

双指针

思路

先把问题转化为选择一些行的末尾放置光标，再通过若干次按方向键，使同一行包含所有的光标，求出光标数量的最大值。

注意到光标之间的距离是不变的。

若光标的放置不在连续的行，那么把这些光标转移到一行后，中间某个没光标的行也必在这行中，所以光标放置行数必连续。

易知应该放到最长的行中。

在每个代码长度后加 1，就可以把光标的位置转化为光标后字符的位置，方便细节处理。

我们预处理出前缀和以快速算出一个区间的总长。

考虑双指针实现计算行数最大值。

代码

#include<bits/stdc++.h>
#define f(n) for(int i=1;i<=n;i++)
#define int long long
#define endl "\n" 
#define IOS cin.tie(0),cout.tie(0),ios::sync_with_stdio(0)
using namespace std;
int T,n,a[200005],s[200005],maxl,ans;
signed main(){
    IOS;cin>>T;
    while(T--){
        cin>>n,maxl=-1,ans=-1;
        f(n)cin>>a[i],a[i]++,s[i]=s[i-1]+a[i],maxl=max(maxl,a[i]);//得到前缀和与长度最大值
        for(int l=1,r=1;r<=n;){//经典的双指针 
            if(s[r]-s[l]<maxl)r++;
            else l++;
            ans=max(ans,r-l);
        }
        cout<<ans<<endl;
    }
    return 0;
}