题解：AtCoder AT_awc0089_c A Walk to Cherry Blossom Viewing

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

AtCoder：C - A Walk to Cherry Blossom Viewing

【题目描述】

In the town where Takahashi lives, there areN NNcherry blossom spots arranged in a straight line, numbered Spot1 11, Spot2 22,… \ldots…, SpotN NNin order. Adjacent spots are connected by promenades, and there exists promenadei ii(1 ≤ i ≤ N − 1 1 \leq i \leq N - 11≤i≤N−1) connecting Spoti iiand Spoti + 1 i + 1i+1. There areN − 1 N - 1N−1promenades in total.

Each Spotj jj(1 ≤ j ≤ N 1 \leq j \leq N1≤j≤N) has a scoreP j P_jPj​representing the beauty of the cherry blossoms at that location. Additionally, each promenadei ii(1 ≤ i ≤ N − 1 1 \leq i \leq N - 11≤i≤N−1) has a maintenance costC i C_iCi​.

Takahashi plans to maintain a contiguous interval of promenades to create a walking course. Specifically, he chooses integersl , r l, rl,r(1 ≤ l ≤ r ≤ N − 1 1 \leq l \leq r \leq N - 11≤l≤r≤N−1) and maintains all of promenadel ll, promenadel + 1 l+1l+1,… \ldots…, promenader rr. By doing so, he can visitallof Spotl ll, Spotl + 1 l+1l+1,… \ldots…, Spotr + 1 r+1r+1along the maintained promenades as his walking course.

Thesatisfactionobtained from the walking course is defined as the sum of the scores of ther − l + 2 r - l + 2r−l+2spots 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, thetotal costof maintenance is:

C l + C l + 1 + ⋯ + C r C_l + C_{l+1} + \cdots + C_rCl​+Cl+1​+⋯+Cr​

Takahashi’s budget isB BB, and he can only choose( l , r ) (l, r)(l,r)such that the total cost is at mostB BB. 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 mostB BB, find themaximum value of the satisfaction.

Note that, due to the constraints, the maintenance cost of each promenade is at mostB BB, sol = r l = rl=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 NN个赏樱景点排成一条直线，按顺序编号为景点1 11、景点2 22、……、景点N NN。相邻景点由散步道连接，存在散步道i ii（1 ≤ i ≤ N − 1 1 \leq i \leq N - 11≤i≤N−1）连接景点i ii和景点i + 1 i + 1i+1。总共有N − 1 N - 1N−1条散步道。

每个景点j jj（1 ≤ j ≤ N 1 \leq j \leq N1≤j≤N）有一个分数P j P_jPj​，代表该地点樱花的美观度。此外，每条散步道i ii（1 ≤ i ≤ N − 1 1 \leq i \leq N - 11≤i≤N−1）有一个维护成本C i C_iCi​。

高桥计划维护一个连续区间的散步道，以创建一条步行路线。具体来说，他选择整数l , r l, rl,r（1 ≤ l ≤ r ≤ N − 1 1 \leq l \leq r \leq N - 11≤l≤r≤N−1），并维护散步道l ll、散步道l + 1 l+1l+1、……、散步道r rr。通过这样做，他可以沿着维护好的散步道访问所有景点l ll、景点l + 1 l+1l+1、……、景点r + 1 r+1r+1作为他的步行路线。

从步行路线中获得的满意度定义为路线中包含的r − l + 2 r - l + 2r−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_rCl​+Cl+1​+⋯+Cr​

高桥的预算是B BB，他只能选择总成本不超过B BB的( l , r ) (l, r)(l,r)。高桥必须选择并维护恰好这样一个区间。

在所有总成本不超过B BB的( l , r ) (l, r)(l,r)选择方式中，求满意度的最大值。

注意，由于约束条件，每条散步道的维护成本不超过B BB，因此l = r l = rl=r（只维护一条散步道）总是满足条件，至少存在一个有效的( l , r ) (l, r)(l,r)选择。

【输入】

N NNB BB
P 1 P_1P1​P 2 P_2P2​… \ldots…P N P_NPN​
C 1 C_1C1​C 2 C_2C2​… \ldots…C N − 1 C_{N-1}CN−1​

• The first line contains an integerN NNrepresenting the number of cherry blossom spots and an integerB BBrepresenting the budget, separated by a space.
• The second line containsN NNintegersP 1 , P 2 , … , P N P_1, P_2, \ldots, P_NP1​,P2​,…,PN​representing the scores of each spot, separated by spaces.
• The third line containsN − 1 N - 1N−1integersC 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 mostB BB.

【输入样例】

5 10 3 1 4 1 5 2 3 4 5

【输出样例】

10

【算法标签】

#双指针

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;// 定义长整型别名，便于处理大数据#defineintlonglong// 定义数组最大容量constintN=500005;// 全局变量声明intn;// 节点数量intb;// 预算上限（可承受的最大连接成本）intp[N];// 每个节点的价值intc[N];// 相邻节点之间的连接成本// 主函数入口（使用signed避免与long long冲突）signedmain(){// 读取节点数量和预算上限cin>>n>>b;// 读取每个节点的价值for(inti=1;i<=n;i++)cin>>p[i];// 读取相邻节点之间的连接成本（共n-1条边）for(inti=1;i<n;i++)cin>>c[i];// 滑动窗口：寻找在预算范围内能获得的最大总价值intans=0;// 记录最大总价值intsumP=p[1];// 当前窗口内的总价值intsumC=0;// 当前窗口内的总连接成本// 右指针从1到n-1移动，不断尝试扩大窗口for(intr=1,l=1;r<n;r++){sumP+=p[r+1];// 将新节点加入窗口sumC+=c[r];// 加上新连接的成本// 如果总成本超过预算，从左端收缩窗口while(l<=r&&sumC>b){sumC-=c[l];// 移除左端的连接成本sumP-=p[l];// 移除左端节点的价值l++;// 左指针右移}// 更新最大总价值ans=max(ans,sumP);}// 输出结果cout<<ans<<endl;return0;}

【运行结果】

5 10 3 1 4 1 5 2 3 4 5 10