题解：P11963 [GESP202503 六级] 环线

· · 题解

begin

P11963 [GESP202503 六级] 环线

前言（渺小）

考试的时候打了一个超级无敌大歪解，个人认为漏洞百出，但是还是成功的骗到了 90\% 的分数。（大概是数据的锅。？）

考后看到标签后恍然大悟，造就了这篇题解。

另：不会单调队列的可以去看看 P1886 滑动窗口 /【模板】单调队列。

思路

我们简化一下题目：截取一个长度 \le n 的序列，使它的和最大。

那么众所周知，如果要让和最大，那么减掉的就越少越好。

所以我们可以先求出破环成链后的 a 数组的前缀和 sum 数组，然后对于每一个 1\le i \le 2n 在确保长度不超过 n 的情况下，减掉一个最小的前缀和，最后取最大值即可。

针对上述思路，单调队列简直再合适不过了。

Code

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll N=4e5+10;
ll n,a[N],sum[N],q[N],head=1,tail,ans=-1e10;
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    // 破环成链
    for (ll i=1;i<=n;i++) cin>>a[i],a[i+n]=a[i];
    // 前缀和
    for (ll i=1;i<=n*2;i++) sum[i]=sum[i-1]+a[i];
    // 单调队列
    for (ll i=1;i<=n*2;i++)
    {
        while (head<=tail && i-q[head]>n) head++; // 确保区间长度合法
        while (head<=tail && sum[q[tail]]>=sum[i]) tail--; // 构造递增队列的
        ans=max(ans,sum[i]-sum[q[head]]); // 取最大值
        q[++tail]=i; // 扔进去
    }
    cout<<ans;
    return 0;
}

end