本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。
欢迎大家订阅我的专栏：算法题解：C++与Python实现！
附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总
【题目来源】
AtCoder：C - Laying Optical Fiber
【题目描述】
Takahashi is an engineer at a telecommunications company. He has been assigned a project to lay new fiber optic cables.
There areN NNrelay stations along a road, and each station is aligned in a straight line. The stations are numbered1 , 2 , … , N 1, 2, \ldots, N1,2,…,Nin order of increasing distance from the starting point of the road, and thei ii-th station is locatedX i X_iXimeters from the starting point (X 1 < X 2 < ⋯ < X N X_1 < X_2 < \cdots < X_NX1<X2<⋯<XN). Activating each stationi iicostsC i C_iCiten-thousand yen.
Takahashi’s project has been allocated a budget ofM MMten-thousand yen. To lay the fiber optic cable, Takahashi can select one contiguous interval of stations. Specifically, he chooses a pair of integers( l , r ) (l, r)(l,r)satisfying1 ≤ l ≤ r ≤ N 1 \leq l \leq r \leq N1≤l≤r≤N, and activates all stations from thel ll-th to ther rr-th. The required cost is the total activation cost of all stations in the chosen interval,∑ i = l r C i \displaystyle\sum_{i=l}^{r} C_ii=l∑rCiten-thousand yen, which must not exceed the budget ofM MMten-thousand yen. Note that the cost of laying cables between stations can be ignored.
When a valid( l , r ) (l, r)(l,r)is chosen under this condition, a fiber optic cable ofX r − X l X_r - X_lXr−Xlmeters can be laid (ifl = r l = rl=r, the length is0 00meters). If there is no interval that fits within the budget, or if Takahashi chooses not to select any interval, nothing is laid, and the cable length is0 00meters.
Find the maximum length of fiber optic cable that Takahashi can lay, in meters.
高桥是一家电信公司的工程师。他被分配了一个铺设新光纤电缆的项目。
沿着一条道路有N NN个中继站，每个站点在一条直线上排列。站点按照距离道路起点的距离递增顺序编号为1 , 2 , … , N 1, 2, \ldots, N1,2,…,N，第i ii个站点位于距离起点X i X_iXi米处（X 1 < X 2 < ⋯ < X N X_1 < X_2 < \cdots < X_NX1<X2<⋯<XN）。激活每个站点i ii的成本为C i C_iCi万日元。
高桥的项目被分配了M MM万日元的预算。为了铺设光纤电缆，高桥可以选择一个连续的站点区间。具体来说，他选择一对满足1 ≤ l ≤ r ≤ N 1 \leq l \leq r \leq N1≤l≤r≤N的整数( l , r ) (l, r)(l,r)，并激活从第l ll个到第r rr个的所有站点。所需成本是所选区间内所有站点的总激活成本，即∑ i = l r C i \displaystyle\sum_{i=l}^{r} C_ii=l∑rCi万日元，这个成本不能超过预算M MM万日元。注意，站点之间铺设电缆的成本可以忽略不计。
当在此条件下选择一个有效的( l , r ) (l, r)(l,r)时，可以铺设长度为X r − X l X_r - X_lXr−Xl米的光纤电缆（如果l = r l = rl=r，则长度为0 00米）。如果没有符合预算的区间，或者高桥选择不选任何区间，则不铺设任何电缆，电缆长度为0 00米。
求高桥可以铺设的光纤电缆的最大长度，单位为米。
【输入】
N NNM MM
X 1 X_1X1C 1 C_1C1
X 2 X_2X2C 2 C_2C2
⋮ \vdots⋮
X N X_NXNC N C_NCN
- The first line contains an integerN NNrepresenting the number of stations and an integerM MMrepresenting the budget (in ten-thousand yen), separated by a space.
- From the 2nd line to the( N + 1 ) (N + 1)(N+1)-th line, information about each station is given.
- The( 1 + i ) (1 + i)(1+i)-th line contains an integerX i X_iXirepresenting the position (in meters) of thei ii-th station and an integerC i C_iCirepresenting the cost (in ten-thousand yen) required to activate that station, separated by a space.
- The stations are given in ascending order of position, and it is guaranteed thatX 1 < X 2 < ⋯ < X N X_1 < X_2 < \cdots < X_NX1<X2<⋯<XN.
【输出】
Print the maximum length of fiber optic cable that Takahashi can lay, in meters, on a single line.
【输入样例】
5 10 1 2 3 3 7 4 12 5 20 6【输出样例】
6【核心思想】
问题分析：给定N NN个按位置升序排列的中继站，每个站点有位置X i X_iXi和激活成本C i C_iCi。需要选择一个连续区间[ l , r ] [l, r][l,r]，使得区间内总成本∑ i = l r C i ≤ M \sum_{i=l}^{r} C_i \leq M∑i=lrCi≤M，同时最大化区间两端的位置差X r − X l X_r - X_lXr−Xl。这是一个**双指针（滑动窗口）**问题，关键在于如何在成本约束下找到最优区间。
算法选择：
- 双指针（滑动窗口）：使用两个指针l ll（左指针）和r rr（右指针）维护一个窗口[ l , r ] [l, r][l,r]，保证窗口内总成本不超过M MM
- 单调性利用：由于站点按位置升序排列，X r − X l X_r - X_lXr−Xl随窗口扩大而增大，但成本约束限制了窗口大小
关键步骤：
- 初始化：l = 1 l = 1l=1（左指针），s u m = 0 sum = 0sum=0（当前窗口总成本），m a x n = 0 maxn = 0maxn=0（最大位置差）
- 扩展窗口（右指针r rr从1 11到N NN）：
- 将第r rr个站点的成本加入窗口：
sum += c[r]
- 将第r rr个站点的成本加入窗口：
- 收缩窗口：当
sum > M时（成本超限）- 不断移除左指针站点的成本：
sum -= c[l] - 左指针右移：
l++
- 不断移除左指针站点的成本：
- 更新答案：如果窗口有效（
l <= r且sum <= M）- 计算当前位置差：
x[r] - x[l] - 更新最大位置差：
maxn = max(maxn, x[r] - x[l])
- 计算当前位置差：
- 输出最大位置差m a x n maxnmaxn
时间/空间复杂度：
- 时间复杂度：O ( N ) O(N)O(N)，每个站点最多被左右指针各访问一次
- 空间复杂度：O ( N ) O(N)O(N)，存储站点位置和成本
双指针（滑动窗口）的核心思想：
- 单调性：右指针r rr只向右移动，左指针l ll也只向右移动，不会回退
- 窗口维护：始终保持窗口[ l , r ] [l, r][l,r]内的总成本不超过预算M MM
- 贪心策略：对于每个右端点r rr，找到最远的左端点l ll使得区间[ l , r ] [l, r][l,r]的成本不超过M MM，此时X r − X l X_r - X_lXr−Xl是以r rr结尾的最大位置差
- 线性扫描：利用双指针的单调性，将暴力枚举的O ( N 2 ) O(N^2)O(N2)优化到O ( N ) O(N)O(N)
- 适用于连续子数组满足某约束条件下的最值问题
【算法标签】
#双指针
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=200005;// 定义数组最大长度intn,m,maxn,sum;// 物品数量n，重量限制m，最大差值maxn，当前重量和sumintx[N],c[N];// 位置数组x，重量数组csignedmain(){cin>>n>>m;// 输入物品数量和重量限制for(inti=1;i<=n;i++)// 遍历读取所有物品cin>>x[i]>>c[i];// 输入物品位置和重量intl=1;// 初始化滑动窗口左指针for(intr=1;r<=n;r++)// 滑动窗口右指针遍历{sum+=c[r];// 将右指针物品加入当前重量while(sum>m&&l<=r)// 如果当前总重量超过限制{sum-=c[l];// 移除左指针物品l++;// 左指针右移}if(l<=r&&sum<=m)// 如果窗口有效且重量不超限{maxn=max(maxn,x[r]-x[l]);// 更新位置最大差值}}cout<<maxn<<endl;// 输出最大差值return0;// 程序正常结束}【运行结果】
5 10 1 2 3 3 7 4 12 5 20 6 6
