题解：P14576 Lamborghini (Remix)

· · 题解

感觉题面很新颖，不过新颖不好理解，我们把它转换成传统题面。

考虑把所有行合并到一行，光标在段首或段尾，开头不能有。

那么根据贪心显然要移动到最长的一段，且光标一定在一个区间内，如果光标在一部分在前，一部分在后，则中间也一定可以选上。

那么问题就变成了：给你一个区间，分成了 n 段，选择尽可能多的连续的段，使得这一整段的总长度小于区间里最大的段 mx。

如图：

   7      4    5       10     2
-------|----|-----|----------|--|

发现第二段和第三段可以塞到第四段里，答案是 3，发现答案就是段数加 1，这就是个滑动窗口板子，维护一个长度为 mx 的队列，遍历入队时更新答案即可。

注意到开头不能有光标，所以选的段为开头的时候不要 +1，而且当选的段长和最大长相等时不要 +1，因为没有位置放 | 了。

代码

int T,n,a[N],mx,ans,sum,q[N],h,t;
signed main(){
    read(T);
    while(T--){
        read(n);mx=sum=h=t=0;ans=1;
        rep(i,1,n){
            read(a[i]);a[i]++;
            mx=max(mx,a[i]);
        }
        h=1;
        rep(i,2,n){
            while(sum+a[i]>mx) sum-=q[h++]; 
            sum+=a[i];q[++t]=a[i];
            ans=max(ans,t-h+1+(sum<mx));
        }
        cout<<ans<<"\n";
    }
    return 0;
}