本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AtCoderC - 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_NX1X2⋯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_{il}^{r} C_iil∑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 rlr, 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_NX1X2⋯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_{il}^{r} C_iil∑rCi万日元这个成本不能超过预算M MM万日元。注意站点之间铺设电缆的成本可以忽略不计。当在此条件下选择一个有效的( l , r ) (l, r)(l,r)时可以铺设长度为X r − X l X_r - X_lXr−Xl米的光纤电缆如果l r l rlr则长度为0 00米。如果没有符合预算的区间或者高桥选择不选任何区间则不铺设任何电缆电缆长度为0 00米。求高桥可以铺设的光纤电缆的最大长度单位为米。【输入】N NNM MMX 1 X_1X1C 1 C_1C1X 2 X_2X2C 2 C_2C2⋮ \vdots⋮X N X_NXNC N C_NCNThe 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)(N1)-th line, information about each station is given.The( 1 i ) (1 i)(1i)-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_NX1X2⋯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_{il}^{r} C_i \leq M∑ilrCi≤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 1l1左指针s u m 0 sum 0sum0当前窗口总成本m a x n 0 maxn 0maxn0最大位置差扩展窗口右指针r rr从1 11到N NN将第r rr个站点的成本加入窗口sum c[r]收缩窗口当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)适用于连续子数组满足某约束条件下的最值问题【算法标签】#双指针【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglongconstintN200005;// 定义数组最大长度intn,m,maxn,sum;// 物品数量n重量限制m最大差值maxn当前重量和sumintx[N],c[N];// 位置数组x重量数组csignedmain(){cinnm;// 输入物品数量和重量限制for(inti1;in;i)// 遍历读取所有物品cinx[i]c[i];// 输入物品位置和重量intl1;// 初始化滑动窗口左指针for(intr1;rn;r)// 滑动窗口右指针遍历{sumc[r];// 将右指针物品加入当前重量while(summlr)// 如果当前总重量超过限制{sum-c[l];// 移除左指针物品l;// 左指针右移}if(lrsumm)// 如果窗口有效且重量不超限{maxnmax(maxn,x[r]-x[l]);// 更新位置最大差值}}coutmaxnendl;// 输出最大差值return0;// 程序正常结束}【运行结果】5 10 1 2 3 3 7 4 12 5 20 6 6
题解：AtCoder AT_awc0083_c Laying Optical Fiber
发布时间：2026/6/12 0:23:06
本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AtCoderC - 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_NX1X2⋯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_{il}^{r} C_iil∑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 rlr, 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_NX1X2⋯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_{il}^{r} C_iil∑rCi万日元这个成本不能超过预算M MM万日元。注意站点之间铺设电缆的成本可以忽略不计。当在此条件下选择一个有效的( l , r ) (l, r)(l,r)时可以铺设长度为X r − X l X_r - X_lXr−Xl米的光纤电缆如果l r l rlr则长度为0 00米。如果没有符合预算的区间或者高桥选择不选任何区间则不铺设任何电缆电缆长度为0 00米。求高桥可以铺设的光纤电缆的最大长度单位为米。【输入】N NNM MMX 1 X_1X1C 1 C_1C1X 2 X_2X2C 2 C_2C2⋮ \vdots⋮X N X_NXNC N C_NCNThe 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)(N1)-th line, information about each station is given.The( 1 i ) (1 i)(1i)-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_NX1X2⋯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_{il}^{r} C_i \leq M∑ilrCi≤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 1l1左指针s u m 0 sum 0sum0当前窗口总成本m a x n 0 maxn 0maxn0最大位置差扩展窗口右指针r rr从1 11到N NN将第r rr个站点的成本加入窗口sum c[r]收缩窗口当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)适用于连续子数组满足某约束条件下的最值问题【算法标签】#双指针【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglongconstintN200005;// 定义数组最大长度intn,m,maxn,sum;// 物品数量n重量限制m最大差值maxn当前重量和sumintx[N],c[N];// 位置数组x重量数组csignedmain(){cinnm;// 输入物品数量和重量限制for(inti1;in;i)// 遍历读取所有物品cinx[i]c[i];// 输入物品位置和重量intl1;// 初始化滑动窗口左指针for(intr1;rn;r)// 滑动窗口右指针遍历{sumc[r];// 将右指针物品加入当前重量while(summlr)// 如果当前总重量超过限制{sum-c[l];// 移除左指针物品l;// 左指针右移}if(lrsumm)// 如果窗口有效且重量不超限{maxnmax(maxn,x[r]-x[l]);// 更新位置最大差值}}coutmaxnendl;// 输出最大差值return0;// 程序正常结束}【运行结果】5 10 1 2 3 3 7 4 12 5 20 6 6
