本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AtCoderA - 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 SST 1 T_1T1T 2 T_2T2… \ldots…T N T_NTNThe 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为常数不影响路径选择只需优化移动距离适用于一维坐标上的遍历覆盖问题核心在于消除冗余往返【算法标签】#贪心【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglong// 将int定义为long long避免总时间计算溢出constintN1000005;// 定义数组最大容量为1000005intn,d,s,ans;// n为货架数量d为相邻货架移动时间s为起始货架编号ans记录最短总时间inta[N];// a[i]表示检查货架i所需的时间signedmain()// 使用signed main配合#define int long long{cinnds;// 读入货架数n、相邻移动时间d、起始货架sfor(inti1;in;i)// 读入每个货架的检查时间{cina[i];ansa[i];// 累加所有货架的检查时间检查时间是固定的与顺序无关}// 计算最优策略下的移动时间// 策略从s出发先走到较近的端点1或n然后一路走到另一端点// 这样只需走一次回头路从s到较近端点其余都是单向移动// tmp从起始货架s到较近端点的距离到1的距离为s-1到n的距离为n-sinttmpmin(s-1,n-s);// 取到左端点(s-1)和右端点(n-s)的较小值anstmp*d;// 加上从s到较近端点的移动时间// 从一端走到另一端需要经过n-1个相邻间隔ans(n-1)*d;// 加上从一端走到另一端的移动时间coutansendl;// 输出最短总时间检查时间移动时间return0;}【运行结果】4 2 2 3 1 4 2 18
` 输出结果是 **9**，因为 `**` 是 Python 中的幂运算符，`3**2` 表示 3 的 2 次方，即 $3^2 = 9$)
