GESP认证C++编程真题解析 | P11963 [GESP202503 六级] 环线-编程实验室

欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶，逐步提升编程能力，助力信息学竞赛备战！

专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。

适合人群：

准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
希望系统学习C++/Python编程的初学者
想要提升算法与编程能力的编程爱好者

附上汇总帖：GESP认证C++编程真题解析 | 汇总

【题目来源】

洛谷：P11963 [GESP202503 六级] 环线 - 洛谷

【题目描述】

小 A 喜欢坐地铁。地铁环线有n nn个车站，依次以1 , 2 , ⋯ , n 1,2,⋯,n1,2,⋯,n标号。车站i ( 1 ≤ i < n ) i (1≤i<n)i(1≤i<n)的下一个车站是车站i + 1 i+1i+1。特殊地，车站n nn的下一个车站是车站1 11。

小 A 会从某个车站出发，乘坐地铁环线到某个车站结束行程，这意味着小 A 至少会经过一个车站。小 A 不会经过一个车站多次。当小 A 乘坐地铁环线经过车站i ii时，小 A 会获得a i a_iai点快乐值。请你安排小 A 的行程，选择出发车站与结束车站，使得获得的快乐值总和最大。

【输入】

第一行，一个正整数n nn，表示车站的数量。

第二行，n nn个整数a i a_iai，分别表示经过每个车站时获得的快乐值。

【输出】

一行，一个整数，表示小 A 能获得的最大快乐值。

【输入样例】

4 -1 2 3 0

【输出样例】

【算法标签】

《洛谷 P11963 环线》 #单调队列# #GESP# #2025#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong// 定义宏，将int替换为long long类型constintN=200005;// 定义数组的最大大小intn;// 输入的数字个数inta[N*2];// 存储输入的数字，并复制一份实现环形处理intsa[N*2];// 前缀和数组intmaxn=-2e18;// 记录最大子段和，初始化为极小值intq[N*2];// 单调队列，用于维护窗口最小值signedmain(){cin>>n;// 输入数字个数// 输入数字并复制一份实现环形处理for(inti=1;i<=n;i++){intx;cin>>x;a[i]=x;a[i+n]=x;// 复制一份，实现环形数组}// 计算前缀和数组for(inti=1;i<=2*n;i++){sa[i]=sa[i-1]+a[i];}// 初始化单调队列inthh=0,tt=-1;// 队列头尾指针// 遍历前缀和数组，寻找最大子段和for(inti=1;i<=2*n;i++){// 维护窗口大小不超过nwhile(hh<=tt&&q[hh]<i-n)hh++;// 计算当前窗口的最大子段和if(hh<=tt){maxn=max(maxn,sa[i]-sa[q[hh]]);}// 维护单调递增队列while(hh<=tt&&sa[q[tt]]>=sa[i])tt--;q[++tt]=i;}cout<<maxn<<endl;// 输出最大子段和return0;}