赛情分析
| A | Correcting the Household Account Book | ⭐ | 模拟 / 前缀和 | 维护总和，每次操作直接减去被清零位置的值即可。 |
| B | Connecting Pipes | ⭐⭐ | 贪心 / 排序 | 将管道按有效长度降序排序，依次选取并维护最大长度，注意每多选一根管道需扣除连接成本K。 |
| C | A Walk to Cherry Blossom Viewing | ⭐⭐⭐ | 双指针（滑动窗口） | 用滑动窗口维护成本不超过预算B的连续散步道区间，动态调整左右指针并更新最大景点分数和。 |
| D | Cheapest Route | ⭐⭐⭐ | Dijkstra最短路 | 边权为两端城市人口乘积，从城市1跑单源最短路，取所有机场城市的最小距离。 |
| E | Painting the Fence | ⭐⭐⭐⭐⭐ | 离散化 + 扫描线 + 差分 | 将区间端点离散化后用扫描线维护当前覆盖集合，利用差分数组统计忽略K个连续指令后的最大覆盖长度。 |
逐题精讲
A题 — 账簿修正
- 定位：签到题
- 核心：本题本质就是维护一个动态变化的数组和。由于每次只把某个位置清零，且每个位置最多被清零一次，所以直接 sum -= a[x] 即可。
- 易错点：无，非常直接的模拟。
- 时间复杂度：
O
(
N
+
Q
)
O(N + Q)
O(N+Q)
B题 — 连接管道
- 定位：简单贪心
- 核心：先计算每根管道的有效长度（生锈的扣除C），按降序排序。选择
M
M
M 根管道的总价值为∑
i
=
1
M
p
i
−
(
M
−
1
)
×
K
\\sum_{i=1}^{M} p_i – (M-1) \\times K
∑i=1Mpi−(M−1)×K。排序后依次累加，过程中维护最大值。 - 易错点：注意
M
=
1
M=1
M=1 时没有连接成本；生锈管道的有效长度不能为负（需与0取max）。 - 时间复杂度：
O
(
N
log
N
)
O(N \\log N)
O(NlogN)
C题 — 赏樱步行路线
- 定位：经典双指针
- 核心：选择散步道区间
[
l
,
r
]
[l, r]
[l,r] 后，覆盖的景点是[
l
,
r
+
1
]
[l, r+1]
[l,r+1]，成本是[
l
,
r
]
[l, r]
[l,r] 的散步道维护费。用滑动窗口维护成本和，超预算时左指针右移。 - 易错点：注意景点数量和散步道数量的关系（
N
N
N 个景点对应N
−
1
N-1
N−1 条散步道），窗口内景点分数和与成本和的索引要对应正确。 - 时间复杂度：
O
(
N
)
O(N)
O(N)
D题 — 最便宜路线
- 定位：最短路模板题
- 核心：无向带权图，边权为
M
u
×
M
v
M_u \\times M_v
Mu×Mv，跑一遍 Dijkstra，最后在所有机场城市中取 dist 最小值。 - 易错点：城市人口乘积可能很大，需使用 long long；注意图是无向的，要建双向边。
- 时间复杂度：
O
(
(
N
+
K
)
log
N
)
O((N + K) \\log N)
O((N+K)logN)
E题 — 粉刷栅栏
- 定位：全场最难，综合技巧题
- 核心：需要忽略恰好
K
K
K 个连续指令，最大化覆盖长度。关键观察是：对于木板的某个位置，如果覆盖它的指令编号是连续的且跨度≤
K
\\le K
≤K，则可以通过选择合适的s
s
s 使得这些指令都被保留。 - 算法细节：
- 离散化：压缩坐标，处理区间端点
- 扫描线：遍历每个离散段，用 set 维护当前覆盖该段的指令编号集合
- 差分：若覆盖当前段的指令编号连续（mx – mn + 1 <= k），则这些指令一定可以被某段
K
K
K 个连续指令包含，通过差分数组记录贡献 - 求答案：对差分数组求前缀和，找到最大覆盖长度
- 易错点：离散化时要加入 r[i] + 1 作为右端点；差分数组的下标处理（mn + 1 和 mn – x）需要仔细推导；注意
K
K
K 个连续指令的起始位置范围是[
1
,
M
−
K
+
1
]
[1, M-K+1]
[1,M−K+1] 或[
0
,
M
−
K
]
[0, M-K]
[0,M−K]（0-indexed）。 - 时间复杂度：
O
(
M
log
M
)
O(M \\log M)
O(MlogM)
题目
A – Correcting the Household Account Book
【题目来源】
AtCoder：A – Correcting the Household Account Book
【题目描述】
Takahashi is keeping a household account book for
N
N
N days.
Takahashi’s account balance is initially
0
0
0 yen. On day
i
i
i
(
1
≤
i
≤
N
)
(1 \\leq i \\leq N)
(1≤i≤N), a transaction of
A
i
A_i
Ai yen is recorded, where a positive value represents a deposit and a negative value represents a withdrawal. Each day’s transaction is applied to the account balance in order (the account balance may become negative during the process). The account balance at the end of day
N
N
N, after all transactions have been applied, is
A
1
+
A
2
+
⋯
+
A
N
A_1 + A_2 + \\cdots + A_N
A1+A2+⋯+AN yen.
However, while reviewing the account book, Takahashi noticed that some transactions were recorded incorrectly. He then performs
Q
Q
Q correction operations in order. In the
j
j
j-th operation
(
1
≤
j
≤
Q
)
(1 \\leq j \\leq Q)
(1≤j≤Q), he changes the transaction amount on day
D
j
D_j
Dj to
0
0
0 yen. Once a day’s transaction amount has been changed to
0
0
0, it remains
0
0
0 in all subsequent operations. In other words, with each operation, the number of days whose transaction amounts have been set to
0
0
0 increases.
After each operation, find the sum of all days’ transaction amounts, that is, the account balance at the end of day
N
N
N.
Note that
D
1
,
D
2
,
…
,
D
Q
D_1, D_2, \\ldots, D_Q
D1,D2,…,DQ are all distinct. In other words, the same day’s transaction amount is never changed more than once.
高桥正在记录一本为期
N
N
N 天的家庭账簿。
高桥的账户余额初始为
0
0
0 日元。在第
i
i
i 天（
1
≤
i
≤
N
1 \\leq i \\leq N
1≤i≤N），记录了一笔金额为
A
i
A_i
Ai 日元的交易，其中正值表示存款，负值表示取款。每天的交易按顺序应用到账户余额上（过程中账户余额可能变为负数）。在第
N
N
N 天结束时，所有交易应用后的账户余额为
A
1
+
A
2
+
⋯
+
A
N
A_1 + A_2 + \\cdots + A_N
A1+A2+⋯+AN 日元。
然而，在复核账簿时，高桥注意到一些交易记录有误。于是他按顺序执行
Q
Q
Q 次更正操作。在第
j
j
j 次操作（
1
≤
j
≤
Q
1 \\leq j \\leq Q
1≤j≤Q）中，他将第
D
j
D_j
Dj 天的交易金额更改为
0
0
0 日元。一旦某天的交易金额被更改为
0
0
0，它在所有后续操作中都将保持为
0
0
0。换句话说，每次操作后，交易金额被设为
0
0
0 的天数会增加。
每次操作后，求所有天数的交易金额之和，即第
N
N
N 天结束时的账户余额。
注意，
D
1
,
D
2
,
…
,
D
Q
D_1, D_2, \\ldots, D_Q
D1,D2,…,DQ 互不相同。也就是说，同一天的交易金额不会被更改超过一次。
【输入】
N
N
N
Q
Q
Q
A
1
A_1
A1
A
2
A_2
A2
⋯
\\cdots
⋯
A
N
A_N
AN
D
1
D_1
D1
D
2
D_2
D2
⋮
\\vdots
⋮
D
Q
D_Q
DQ
- The first line contains an integer
N
N
N representing the number of days in the account book and an integerQ
Q
Q representing the number of correction operations, separated by a space. - The second line contains
N
N
N integersA
1
,
A
2
,
…
,
A
N
A_1, A_2, \\ldots, A_N
A1,A2,…,AN representing the transaction amounts for each day, separated by spaces.A
i
A_i
Ai is the transaction amount on dayi
i
i. - Among the following
Q
Q
Q lines, thej
j
j-th line (the(
2
+
j
)
(2 + j)
(2+j)-th line overall) contains a single integerD
j
D_j
Dj representing the day whose transaction amount is changed to0
0
0 in thej
j
j-th operation.
【输出】
Q
Q
Q lines. On the
j
j
j-th line, print the sum of all days’ transaction amounts (the account balance at the end of day
N
N
N) after performing all operations from the
1
1
1-st through the
j
j
j-th.
【输入样例】
5 3
100 -50 200 -30 80
2
4
1
【输出样例】
350
380
280
【算法标签】
#模拟
【代码详解】
#include <bits/stdc++.h>
using namespace std;
// 定义长整型别名，便于处理大数据
#define int long long
// 定义数组最大容量
const int N = 200005;
// 全局变量声明
int n; // 数组长度
int q; // 查询次数
int a[N]; // 存储原始数组元素
// 主函数入口（使用signed避免与long long冲突）
signed main()
{
// 读取数组长度和查询次数
cin >> n >> q;
// 计算所有元素的总和
int sum = 0;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
sum += a[i]; // 累加每个元素到总和
}
// 处理每个查询
while (q—)
{
int x; // 要删除的元素下标
cin >> x;
sum -= a[x]; // 从总和中减去该元素
cout << sum << endl; // 输出剩余元素的和
}
return 0;
}
【运行结果】
5 3
100 -50 200 -30 80
2
350
4
380
1
280
B – Connecting Pipes
【题目来源】
AtCoder：B – Connecting Pipes
【题目描述】
Takahashi has
N
N
N pipes. The length of the
i
i
i-th pipe is
A
i
A_i
Ai.
Some pipes are rusted. If the
i
i
i-th pipe is rusted,
B
i
=
1
B_i = 1
Bi=1; if it is not rusted,
B
i
=
0
B_i = 0
Bi=0. Due to rust, the effective usable length of a rusted pipe is reduced to
max
(
A
i
−
C
,
0
)
\\max(A_i – C, 0)
max(Ai−C,0). The effective length of a non-rusted pipe is
A
i
A_i
Ai.
Takahashi freely selects at least 1 and at most
N
N
N of these
N
N
N pipes (each pipe can be selected at most once) and connects them in a line to form a single pipe. If only one pipe is selected, its effective length directly becomes the length of the finished pipe. If two or more pipes are selected, joint parts are used to connect the pipes, so the finished pipe’s length is reduced by
K
K
K for each connection point.
If the number of selected pipes is
M
M
M, there are
M
−
1
M – 1
M−1 connection points, so the length of the finished pipe is given by the following formula:
(
sum of effective lengths of the
M
selected pipes
)
−
(
M
−
1
)
×
K
(\\text{sum of effective lengths of the } M \\text{ selected pipes}) – (M – 1) \\times K
(sum of effective lengths of the M selected pipes)−(M−1)×K
Takahashi wants the length of the finished pipe to be at least
D
D
D. When the combination and number of pipes are chosen optimally, find the maximum possible length of the finished pipe. If the maximum value is at least
D
D
D, output that value; if it is impossible to achieve a length of
D
D
D or more regardless of the selection, output
−
1
-1
−1.
高桥有
N
N
N 根管道。第
i
i
i 根管道的长度为
A
i
A_i
Ai。
有些管道生锈了。如果第
i
i
i 根管道生锈了，则
B
i
=
1
B_i = 1
Bi=1；如果没有生锈，则
B
i
=
0
B_i = 0
Bi=0。由于生锈，生锈管道的有效可用长度减少为
max
(
A
i
−
C
,
0
)
\\max(A_i – C, 0)
max(Ai−C,0)。未生锈管道的有效长度为
A
i
A_i
Ai。
高桥从这
N
N
N 根管道中自由选择至少 1 根且至多
N
N
N 根（每根管道最多被选择一次），并将它们连接成一条线，形成一根单一的管道。如果只选择一根管道，其有效长度直接成为成品管道的长度。如果选择两根或多根管道，则需要使用接头来连接管道，因此成品管道的长度会因每个连接点而减少
K
K
K。
如果选择的管道数量为
M
M
M，则有
M
−
1
M – 1
M−1 个连接点，因此成品管道的长度由以下公式给出：
(
所选
M
根管道的有效长度之和
)
−
(
M
−
1
)
×
K
(\\text{所选 } M \\text{ 根管道的有效长度之和}) – (M – 1) \\times K
(所选 M 根管道的有效长度之和)−(M−1)×K
高桥希望成品管道的长度至少为
D
D
D。当最优地选择管道的组合和数量时，求成品管道的最大可能长度。如果最大值至少为
D
D
D，输出该值；如果无论如何选择都无法达到
D
D
D 或以上的长度，输出
−
1
-1
−1。
【输入】
N
N
N
D
D
D
K
K
K
C
C
C
A
1
A_1
A1
B
1
B_1
B1
A
2
A_2
A2
B
2
B_2
B2
⋮
\\vdots
⋮
A
N
A_N
AN
B
N
B_N
BN
- The first line contains the number of pipes
N
N
N, the required lengthD
D
D, the length reduction per connection pointK
K
K, and the length reduction due to rustC
C
C, separated by spaces. - From the 2nd line to the
(
N
+
1
)
(N + 1)
(N+1)-th line, the information for each pipe is given. - The
(
1
+
i
)
(1 + i)
(1+i)-th line contains the lengthA
i
A_i
Ai of thei
i
i-th pipe andB
i
B_i
Bi (0
0
0 or1
1
1) indicating whether it is rusted, separated by spaces.
【输出】
If the maximum possible length of the finished pipe is at least
D
D
D, output that maximum value on a single line. If it is impossible to achieve a length of at least
D
D
D, output
−
1
-1
−1 on a single line.
【输入样例】
4 15 3 4
10 0
8 1
7 0
6 1
【输出样例】
15
【算法标签】
#贪心
【代码详解】
#include <bits/stdc++.h>
using namespace std;
// 定义长整型别名，便于处理大数据
#define int long long
// 定义数组最大容量
const int N = 100005;
// 全局变量声明
int n; // 物品数量
int d; // 目标阈值
int k; // 基础收益
int c; // 成本抵扣值
int maxn = –1e9; // 记录最大累计收益，初始化为极小值
int p[N]; // 存储每个物品的实际收益
// 主函数入口（使用signed避免与long long冲突）
signed main()
{
// 读取物品数量、目标阈值、基础收益和成本抵扣值
cin >> n >> d >> k >> c;
// 读取每个物品的信息并计算实际收益
for (int i = 1; i <= n; i++)
{
int a, b; // a: 原始收益, b: 物品类型标志
cin >> a >> b;
if (b == 1) // 如果是特殊类型物品，扣除成本c
a = max(0LL, a – c); // 收益不能为负数
p[i] = a; // 存储实际收益
}
// 将实际收益按降序排序（优先选取高收益物品）
sort(p + 1, p + n + 1, greater<int>());
// 贪心选择：依次选取收益最高的物品
int sum = k; // 初始收益为基础收益k
for (int i = 1; i <= n; i++)
{
sum += p[i] – k; // 选取第i个物品后的累计收益变化
maxn = max(maxn, sum); // 更新最大累计收益
}
// 判断是否达到目标阈值
if (maxn >= d)
cout << maxn << endl; // 输出最大累计收益
else
cout << –1 << endl; // 无法达到目标，输出-1
return 0;
}
【运行结果】
4 15 3 4
10 0
8 1
7 0
6 1
15
C – A Walk to Cherry Blossom Viewing
【题目来源】
AtCoder：C – A Walk to Cherry Blossom Viewing
【题目描述】
In the town where Takahashi lives, there are
N
N
N cherry blossom spots arranged in a straight line, numbered Spot
1
1
1, Spot
2
2
2,
…
\\ldots
…, Spot
N
N
N in order. Adjacent spots are connected by promenades, and there exists promenade
i
i
i (
1
≤
i
≤
N
−
1
1 \\leq i \\leq N – 1
1≤i≤N−1) connecting Spot
i
i
i and Spot
i
+
1
i + 1
i+1. There are
N
−
1
N – 1
N−1 promenades in total.
Each Spot
j
j
j (
1
≤
j
≤
N
1 \\leq j \\leq N
1≤j≤N) has a score
P
j
P_j
Pj representing the beauty of the cherry blossoms at that location. Additionally, each promenade
i
i
i (
1
≤
i
≤
N
−
1
1 \\leq i \\leq N – 1
1≤i≤N−1) has a maintenance cost
C
i
C_i
Ci.
Takahashi plans to maintain a contiguous interval of promenades to create a walking course. Specifically, he chooses integers
l
,
r
l, r
l,r (
1
≤
l
≤
r
≤
N
−
1
1 \\leq l \\leq r \\leq N – 1
1≤l≤r≤N−1) and maintains all of promenade
l
l
l, promenade
l
+
1
l+1
l+1,
…
\\ldots
…, promenade
r
r
r. By doing so, he can visit all of Spot
l
l
l, Spot
l
+
1
l+1
l+1,
…
\\ldots
…, Spot
r
+
1
r+1
r+1 along the maintained promenades as his walking course.
The satisfaction obtained from the walking course is defined as the sum of the scores of the
r
−
l
+
2
r – l + 2
r−l+2 spots included in the course:
P
l
+
P
l
+
1
+
⋯
+
P
r
+
1
P_l + P_{l+1} + \\cdots + P_{r+1}
Pl+Pl+1+⋯+Pr+1
On the other hand, the total cost of maintenance is:
C
l
+
C
l
+
1
+
⋯
+
C
r
C_l + C_{l+1} + \\cdots + C_r
Cl+Cl+1+⋯+Cr
Takahashi’s budget is
B
B
B, and he can only choose
(
l
,
r
)
(l, r)
(l,r) such that the total cost is at most
B
B
B. Takahashi must choose and maintain exactly one such interval.
Among all ways to choose
(
l
,
r
)
(l, r)
(l,r) such that the total cost is at most
B
B
B, find the maximum value of the satisfaction.
Note that, due to the constraints, the maintenance cost of each promenade is at most
B
B
B, so
l
=
r
l = r
l=r (maintaining just one promenade) always satisfies the condition, and there exists at least one valid choice of
(
l
,
r
)
(l, r)
(l,r).
在高桥居住的小镇上，有
N
N
N 个赏樱景点排成一条直线，按顺序编号为景点
1
1
1、景点
2
2
2、……、景点
N
N
N。相邻景点由散步道连接，存在散步道
i
i
i（
1
≤
i
≤
N
−
1
1 \\leq i \\leq N – 1
1≤i≤N−1）连接景点
i
i
i 和景点
i
+
1
i + 1
i+1。总共有
N
−
1
N – 1
N−1 条散步道。
每个景点
j
j
j（
1
≤
j
≤
N
1 \\leq j \\leq N
1≤j≤N）有一个分数
P
j
P_j
Pj，代表该地点樱花的美观度。此外，每条散步道
i
i
i（
1
≤
i
≤
N
−
1
1 \\leq i \\leq N – 1
1≤i≤N−1）有一个维护成本
C
i
C_i
Ci。
高桥计划维护一个连续区间的散步道，以创建一条步行路线。具体来说，他选择整数
l
,
r
l, r
l,r（
1
≤
l
≤
r
≤
N
−
1
1 \\leq l \\leq r \\leq N – 1
1≤l≤r≤N−1），并维护散步道
l
l
l、散步道
l
+
1
l+1
l+1、……、散步道
r
r
r。通过这样做，他可以沿着维护好的散步道访问所有景点
l
l
l、景点
l
+
1
l+1
l+1、……、景点
r
+
1
r+1
r+1 作为他的步行路线。
从步行路线中获得的满意度定义为路线中包含的
r
−
l
+
2
r – l + 2
r−l+2 个景点的分数之和：
P
l
+
P
l
+
1
+
⋯
+
P
r
+
1
P_l + P_{l+1} + \\cdots + P_{r+1}
Pl+Pl+1+⋯+Pr+1
另一方面，维护的总成本为：
C
l
+
C
l
+
1
+
⋯
+
C
r
C_l + C_{l+1} + \\cdots + C_r
Cl+Cl+1+⋯+Cr
高桥的预算是
B
B
B，他只能选择总成本不超过
B
B
B 的
(
l
,
r
)
(l, r)
(l,r)。高桥必须选择并维护恰好这样一个区间。
在所有总成本不超过
B
B
B 的
(
l
,
r
)
(l, r)
(l,r) 选择方式中，求满意度的最大值。
注意，由于约束条件，每条散步道的维护成本不超过
B
B
B，因此
l
=
r
l = r
l=r（只维护一条散步道）总是满足条件，至少存在一个有效的
(
l
,
r
)
(l, r)
(l,r) 选择。
【输入】
N
N
N
B
B
B
P
1
P_1
P1
P
2
P_2
P2
…
\\ldots
…
P
N
P_N
PN
C
1
C_1
C1
C
2
C_2
C2
…
\\ldots
…
C
N
−
1
C_{N-1}
CN−1
- The first line contains an integer
N
N
N representing the number of cherry blossom spots and an integerB
B
B representing the budget, separated by a space. - The second line contains
N
N
N integersP
1
,
P
2
,
…
,
P
N
P_1, P_2, \\ldots, P_N
P1,P2,…,PN representing the scores of each spot, separated by spaces. - The third line contains
N
−
1
N – 1
N−1 integersC
1
,
C
2
,
…
,
C
N
−
1
C_1, C_2, \\ldots, C_{N-1}
C1,C2,…,CN−1 representing the maintenance costs of each promenade, separated by spaces.
【输出】
Print in one line the maximum satisfaction among all maintenance intervals whose total cost is at most
B
B
B.
【输入样例】
5 10
3 1 4 1 5
2 3 4 5
【输出样例】
10
【核心思想】
问题分析：给定
N
N
N 个景点的分数
P
j
P_j
Pj 和
N
−
1
N-1
N−1 条散步道的维护成本
C
i
C_i
Ci，选择一段连续的散步道区间
[
l
,
r
]
[l, r]
[l,r]，使得维护总成本不超过预算
B
B
B，同时最大化覆盖的景点分数之和
P
l
+
P
l
+
1
+
⋯
+
P
r
+
1
P_l + P_{l+1} + \\cdots + P_{r+1}
Pl+Pl+1+⋯+Pr+1。这是一个**双指针（滑动窗口）**问题，关键在于维护一个满足成本约束的窗口，并动态调整窗口大小。
算法选择：
- 双指针（滑动窗口）：用左右两个指针维护一个满足成本约束的区间
- 前缀和优化：维护当前窗口内的景点分数之和与散步道成本之和
- 贪心调整：当成本超过预算时，从左端收缩窗口
关键步骤：
- 初始化：
- ans = 0：记录最大满意度
- sumP = p[1]：当前窗口内的景点分数之和
- sumC = 0：当前窗口内的散步道成本之和
- l = 1：左指针
- 右指针扩展（遍历
r
r
r 从1
1
1 到n
−
1
n-1
n−1）：- sumP += p[r+1]：将新景点加入窗口
- sumC += c[r]：加上新散步道的成本
- 左指针收缩（当 sumC > b 时）：
- sumC -= c[l]：移除左端散步道的成本
- sumP -= p[l]：移除左端景点的分数
- l++：左指针右移
- 更新答案：ans = max(ans, sumP)
时间/空间复杂度：
- 时间复杂度：
O
(
N
)
O(N)
O(N)，每个元素最多被左右指针各访问一次 - 空间复杂度：
O
(
N
)
O(N)
O(N)，存储景点分数和散步道成本数组
双指针的核心思想：
- 窗口维护：用左右指针维护一个满足约束条件的连续区间
- 单调性：右指针只向右移动，左指针根据条件调整
- 贪心策略：当窗口不满足条件时，从左端收缩，保证窗口内始终满足约束
- 最优性：每个位置作为右端点时，都找到了满足条件的最左端点
- 适用于子数组/子区间最值、约束条件下的区间选择类问题
【算法标签】
#双指针
【代码详解】
#include <bits/stdc++.h>
using namespace std;
// 定义长整型别名，便于处理大数据
#define int long long
// 定义数组最大容量
const int N = 500005;
// 全局变量声明
int n; // 节点数量
int b; // 预算上限（可承受的最大连接成本）
int p[N]; // 每个节点的价值
int c[N]; // 相邻节点之间的连接成本
// 主函数入口（使用signed避免与long long冲突）
signed main()
{
// 读取节点数量和预算上限
cin >> n >> b;
// 读取每个节点的价值
for (int i = 1; i <= n; i++)
cin >> p[i];
// 读取相邻节点之间的连接成本（共n-1条边）
for (int i = 1; i < n; i++)
cin >> c[i];
// 滑动窗口：寻找在预算范围内能获得的最大总价值
int ans = 0; // 记录最大总价值
int sumP = p[1]; // 当前窗口内的总价值
int sumC = 0; // 当前窗口内的总连接成本
// 右指针从1到n-1移动，不断尝试扩大窗口
for (int r = <span class=\"token n
