专栏文章

题解：P14576 Lamborghini (Remix)

lleather_handbag
P14576题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min23hq5
此快照首次捕获于
2025/12/01 19:18
3 个月前
此快照最后确认于
2025/12/01 19:18
3 个月前
查看原文
感觉题面很新颖，不过新颖不好理解，我们把它转换成传统题面。
考虑把所有行合并到一行，光标在段首或段尾，开头不能有。
那么根据贪心显然要移动到最长的一段，且光标一定在一个区间内，如果光标在一部分在前，一部分在后，则中间也一定可以选上。
那么问题就变成了：给你一个区间，分成了 nn 段，选择尽可能多的连续的段，使得这一整段的总长度小于区间里最大的段 mxmx。
如图：
CPP
   7      4    5       10     2
-------|----|-----|----------|--|
发现第二段和第三段可以塞到第四段里，答案是 33，发现答案就是段数加 11，这就是个滑动窗口板子，维护一个长度为 mxmx 的队列，遍历入队时更新答案即可。
注意到开头不能有光标，所以选的段为开头的时候不要 +1+1，而且当选的段长和最大长相等时不要 +1+1，因为没有位置放 | 了。

代码

CPP
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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...