本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。
欢迎大家订阅我的专栏：算法题解：C++与Python实现！
附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总
【题目来源】
AtCoder：A - Warehouse Package Inspection
【题目描述】
高橋负责检查一个大仓库中的货物。仓库里N NN个货架排成一条直线，按顺序编号为1 11到N NN。从货架i ii移动到货架j jj需要∣ i − j ∣ × D |i - j| \times D∣i−j∣×D分钟，其中D DD是一个正整数，表示相邻货架之间的移动时间（单位：分钟）。
每个货架上都有需要检查的货物，检查货架i ii上的货物需要T i T_iTi分钟。检查必须在货架前进行，不能在移动过程中进行。此外，高橋必须完成当前货架的检查后才能开始移动去下一个货架；检查和移动不能同时进行。虽然他可能会在移动过程中经过其他货架，但仅仅经过不算作检查。要检查它们，他必须再次移动到该货架并停下。
高橋最初在货架S SS前面。他可以自由选择先检查哪个货架。高橋从货架S SS前面移动到第一个要检查的货架，并在那里进行检查。如果他选择先检查货架S SS，他可以立即开始检查，移动时间为0 00分钟。
高橋必须恰好检查所有N NN个货架一次。他检查货架的顺序可以自由选择。一旦最后一个货架的检查完成，工作即结束，他不需要返回起始位置。
求完成所有货架货物检查所需的最短总时间（所有移动时间与所有检查时间之和）。
【输入】
N NND DDS SS
T 1 T_1T1T 2 T_2T2… \ldots…T N T_NTN
- The first line contains three space-separated integers:N NN, the number of shelves;D DD, the travel time between adjacent shelves; andS SS, the starting shelf number.
- The second line containsN NNspace-separated integersT 1 , T 2 , … , T N T_1, T_2, \ldots, T_NT1,T2,…,TN, representing the time required to inspect the goods on each shelf.
【输出】
Print the minimum total time (travel time + inspection time) to inspect the goods on all shelves exactly once in a single line.
【输入样例】
4 2 2 3 1 4 2【输出样例】
18【核心思想】
问题分析：给定N NN个排成直线的货架，起始位置为货架S SS，检查货架i ii需T i T_iTi分钟，相邻货架移动耗时D DD。要求恰好检查所有N NN个货架一次，求移动时间 + 检查时间的最小值。检查时间总和固定，因此问题转化为最小化移动时间。
算法选择：
- 贪心策略：从起始点S SS出发，先走向较近的端点（1 11或N NN），再一路走向另一端点
- 关键观察：要覆盖[ 1 , N ] [1, N][1,N]所有点，最优路径是"从S SS到一端，再到另一端"的连续遍历，避免来回折返
关键步骤：
- 固定成本累加：
ans = ΣT_i，检查时间与顺序无关，直接累加 - 计算最优移动路径：
- 到较近端点的距离：
tmp = min(S - 1, N - S) - 从S SS先到较近端点，耗时
tmp × D - 再从该端点走到另一端点，需经过N − 1 N - 1N−1个间隔，耗时
(N - 1) × D
- 到较近端点的距离：
- 总移动时间：
tmp × D + (N - 1) × D，即ans += tmp * d + (n - 1) * d
- 固定成本累加：
时间/空间复杂度：
- 时间复杂度：O ( N ) O(N)O(N)，读入N NN个检查时间并累加
- 空间复杂度：O ( N ) O(N)O(N)，存储检查时间数组（可优化至O ( 1 ) O(1)O(1)）
贪心策略的核心思想：
- 端点覆盖必然性：要检查所有货架，路径必须覆盖区间[ 1 , N ] [1, N][1,N]，因此至少需要从一端走到另一端，基础移动距离为N − 1 N - 1N−1
- 起始点偏移优化：从S SS出发，先向较近端点移动可减少"回头路"——若先走远端点，会多走∣ S − 远端 ∣ − ∣ S − 近端 ∣ |S - \text{远端}| - |S - \text{近端}|∣S−远端∣−∣S−近端∣的重复距离
- 无折返最优：直线上一维覆盖问题，不折返的路径总长度最小，等价于"从S SS出发的区间覆盖"
- 检查时间独立性：Σ T i ΣT_iΣTi为常数，不影响路径选择，只需优化移动距离
- 适用于一维坐标上的遍历覆盖问题，核心在于消除冗余往返
【算法标签】
#贪心
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong// 将int定义为long long，避免总时间计算溢出constintN=1000005;// 定义数组最大容量为1000005intn,d,s,ans;// n为货架数量，d为相邻货架移动时间，s为起始货架编号，ans记录最短总时间inta[N];// a[i]表示检查货架i所需的时间signedmain()// 使用signed main配合#define int long long{cin>>n>>d>>s;// 读入货架数n、相邻移动时间d、起始货架sfor(inti=1;i<=n;i++)// 读入每个货架的检查时间{cin>>a[i];ans+=a[i];// 累加所有货架的检查时间（检查时间是固定的，与顺序无关）}// 计算最优策略下的移动时间：// 策略：从s出发，先走到较近的端点（1或n），然后一路走到另一端点// 这样只需走一次"回头路"（从s到较近端点），其余都是单向移动// tmp：从起始货架s到较近端点的距离（到1的距离为s-1，到n的距离为n-s）inttmp=min(s-1,n-s);// 取到左端点(s-1)和右端点(n-s)的较小值ans+=tmp*d;// 加上从s到较近端点的移动时间// 从一端走到另一端需要经过n-1个相邻间隔ans+=(n-1)*d;// 加上从一端走到另一端的移动时间cout<<ans<<endl;// 输出最短总时间（检查时间+移动时间）return0;}【运行结果】
4 2 2 3 1 4 2 18
