题解：P14576 Lamborghini (Remix)

TFX_Y · 2025-11-23 18:12:26 · 题解

思路

由于光标可以任意移动，那么肯定是最长的那行能容纳的光标数最多。

因为如果一些光标能被段行容纳，那么经过有限次的移动一定也可以移动到长行上面，而长行上面有更多的空间可以容纳更多的光标。

因此，我们可以枚举并计算每一行的光标如果移动到最长的那一行的开头，后面能容纳多少光标。

为了方便计算，我们可以求一个光标距离的前缀和，并二分查找最长行最后一个光标在前缀和数组中的位置。

答案即为最后一个光标在前缀和数组中的位置减去我们枚举的光标在前缀和数组中的位置的最大值。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
void st(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
const int nm=1e6+10;
int t,n,maxx,ans;
int a[nm],sum[nm];
int solve(){
    cin>>n;
    ans=maxx=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]++;
        maxx=max(maxx,a[i]);
        sum[i]=sum[i-1]+a[i];
    }
    for(int i=1;i<=n;i++){
        int pos=lower_bound(sum+1,sum+n+1,sum[i]+maxx)-sum;
        ans=max(ans,pos-i);
    }
    return max(1ll,ans);
}
signed main(){
    st();
    cin>>t;
    while(t--) cout<<solve()<<'\n';
    return 0;
}