本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AtCoderB - A Single Strike of Dominoes【题目描述】There areN NNpillars lined up in a row in front of Takahashi. The durability of thei ii-th pillar from the left isA i A_iAi​.Takahashi simultaneously applies the same forceX XXto all pillars. Each pillar that receives the impact has its durability decreased byX XX.After that, a chain reaction propagates from left to right. Specifically, when a pillar collapses (its durability becomes0 00or less), the durability of the pillar immediately to its right decreases by an additional1 11. If this causes the right neighbor to also collapse, the durability of the pillar immediately to its right decreases by1 11as well. This chain continues to the right until a pillar does not collapse. Note that if the rightmost pillar collapses, no further chain reaction occurs.In summary, whether each pillar collapses is determined from left to right by the following rule: in addition to the direct impactX XX, a pillar receives an additional1 11damage if the pillar immediately to its left has collapsed.Find the minimum value ofX XXrequired to collapse all pillars.X XXmust be a positive integer.高橋面前有一排N NN根柱子。从左数第i ii根柱子的耐久度为A i A_iAi​。高橋同时对所有柱子施加相同的力X XX。每根受到冲击的柱子耐久度减少X XX。之后连锁反应从左向右传播。具体地当一根柱子倒塌耐久度变为0 00或以下时其右侧相邻柱子的耐久度额外减少1 11。如果这导致右侧相邻柱子也倒塌则再往右一根柱子的耐久度也减少1 11。该连锁反应持续向右传播直到某根柱子没有倒塌为止。注意如果最右边的柱子倒塌则不再发生进一步的连锁反应。总之每根柱子是否倒塌按从左到右的顺序由以下规则决定除了直接冲击X XX之外如果其左侧相邻柱子已经倒塌则该柱子额外受到1 11点伤害。求使所有柱子都倒塌所需的最小X XX值。X XX必须是正整数。【输入】The input is given in the following format.N NNA 1 A_1A1​A 2 A_2A2​… \ldots…A N A_NAN​The first line gives the number of pillarsN NN.The second line givesN NNintegersA 1 , A 2 , … , A N A_1, A_2, \ldots, A_NA1​,A2​,…,AN​representing the durability of each pillar, separated by spaces.【输出】Print the minimum value of the forceX XXrequired to collapse all pillars in a single line.【输入样例】4 2 3 2 4【输出样例】3【核心思想】问题分析给定N NN根柱子的耐久度A i A_iAi​需要找到一个最小的正整数X XX使得所有柱子倒塌。倒塌规则为每根柱子先受到X XX的直接伤害然后从左到右检查若第i ii根柱子倒塌耐久度≤ 0 \leq 0≤0则第i 1 i1i1根柱子额外受到1 11点伤害。该问题具有单调性——若X XX能使所有柱子倒塌则任何大于X XX的值也一定能。算法选择整数二分利用可行性随X XX增大而单调不减的性质在值域[ 1 , 10 9 ] [1, 10^9][1,109]上二分查找最小可行X XX模拟验证check函数对于给定的X XX按照题目规则模拟连锁反应判断是否能倒塌所有柱子关键步骤二分边界左边界l 1 l 1l1右边界r 10 9 r 10^9r109X XX的最大可能值二分过程取中点m i d ⌊ l r 2 ⌋ mid \lfloor \frac{l r}{2} \rfloormid⌊2lr​⌋调用check(mid)模拟验证所有柱子先减去X XXb[i] \max(0, A_i - X)从左到右传播连锁反应若b [ i ] 0 b[i] 0b[i]0则b [ i 1 ] max ⁡ ( 0 , b [ i 1 ] − 1 ) b[i1] \max(0, b[i1] - 1)b[i1]max(0,b[i1]−1)检查是否所有b [ i ] 0 b[i] 0b[i]0若check(mid)为真r m i d r midrmid尝试更小的X XX若check(mid)为假l m i d 1 l mid 1lmid1需要更大的X XX输出l ll最小可行X XX时间/空间复杂度时间复杂度O ( N log ⁡ C ) O(N \log C)O(NlogC)其中C 10 9 C 10^9C109为X XX的值域范围。每次check模拟O ( N ) O(N)O(N)二分约log ⁡ C \log ClogC次空间复杂度O ( N ) O(N)O(N)原数组A [ 1.. N ] A[1..N]A[1..N]和临时模拟数组B [ 1.. N ] B[1..N]B[1..N]整数二分的核心思想单调性利用若X XX可行则所有X ′ X X XX′X也可行因此可行解集合具有单调性适合二分验证分离将寻找最优解与验证可行性分离通过高效的模拟验证配合二分快速缩小搜索范围边界处理使用max(0, ...)防止耐久度变为负数避免连锁反应过度传播连锁传播顺序必须严格从左到右依次判断因为第i ii根是否倒塌会影响第i 1 i1i1根的状态适用于具有单调性的最优化问题将求解转化为判定问题 二分搜索的经典模式【算法标签】#整数二分【代码详解】#includebits/stdc.husingnamespacestd;constintN500005;// 最大柱子数量intn;// 柱子数量inta[N],b[N];// a[i]: 第i根柱子的原始耐久度, b[i]: 模拟时的临时耐久度// 检查当施加的力为x时是否能使所有柱子倒塌boolcheck(intx){// 复制原始耐久度到临时数组避免修改原数组memcpy(b,a,sizeof(a));// 第一步所有柱子受到直接冲击xfor(inti1;in;i)b[i]max(0,b[i]-x);// 第二步连锁反应从左到右传播// 如果第i根柱子倒塌耐久度为0则第i1根额外受到1点伤害for(inti1;in;i){if(b[i]0)// 第i根柱子倒塌b[i1]max(0,b[i1]-1);// 右侧相邻柱子额外减1不低于0}// 检查是否所有柱子都倒塌耐久度都为0for(inti1;in;i){if(b[i]0)// 存在未倒塌的柱子returnfalse;}returntrue;// 所有柱子都倒塌}intmain(){cinn;// 读入柱子数量// 读入每根柱子的耐久度for(inti1;in;i)cina[i];// 二分查找最小的Xintl1,r1e9;// X的范围[1, 1e9]while(lr){intmid(lr)/2;// 取中间值if(check(mid))// mid可行尝试更小的Xrmid;else// mid不可行需要更大的Xlmid1;}// 输出最小的Xcoutlendl;return0;}【运行结果】4 2 3 2 4 3