专栏文章

题解：P11963 [GESP202503 六级] 环线

LL0_0
P11963题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@miptsrt0
此快照首次捕获于
2025/12/03 17:49
3 个月前
此快照最后确认于
2025/12/03 17:49
3 个月前
查看原文

解析

在 a1,⋯ ,ana_1,\cdots,a_n 组成的环中，选取最大的连续和。
遇到环，就先破环成链，为了减少分类讨论，我们将链复制一条，也就是要 an+i=aia_{n+i}=a_i，此时问题转化成了，对 r−l+1≤nr-l+1\le n 时求最大的 al+al+1+⋯+ara_l+a_{l+1}+\cdots+a_r，首先进行前缀和，令 sumi=∑l=1iaisum_i=\sum_{l=1}^ia_i，则就是要求 sumr−suml−1sum_r-sum_{l-1} 的最大值，此时直接枚举 l,rl,r，时间复杂度为 O(n2)\mathcal{O}\left(n^2\right)，所以要优化。
于是再定义一个数组 bib_i 表示在区间 [max⁡(0,i−n+1),i][\max(0,i-n+1),i] 的最小 sumjsum_j 值，这个类似滑动窗口，可以使用单调队列来完成。于是最终答案就是 max⁡(sumi−bi−1)\max(sum_i-b_{i-1})，时间复杂度为 O(n)\mathcal{O}(n)。

代码

注意开long long。
CPP
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 4e5+1;
ll n, a[N], sum[N], b[N], ans=-2e18;
deque<ll> q;
// b[i]: [i-n+1, i-1]中最小的sum[i]

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){cin>>a[i]; a[i+n]=a[i];}
    for(int i=1;i<=n*2;i++) sum[i] = sum[i-1] + a[i];
    for(int i=1;i<=n*2;i++){
        while(!q.empty() && q.front() <= i-n) q.pop_front();
        while(!q.empty() && sum[q.back()] >= sum[i]) q.pop_back();
        q.push_back(i);
        b[i] = sum[q.front()];
    }
    for(int i=1;i<=n*2;i++) ans = max(ans, sum[i] - b[i-1]);
    cout << ans;
}

评论

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

正在加载评论...