题解：AtCoder AT_awc0101_b A Single Strike of Dominoes
本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。
欢迎大家订阅我的专栏：算法题解：C++与Python实现！
附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总
【题目来源】
AtCoder：B - 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 NN
A 1 A_1A1A 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,…,ANrepresenting 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 i+1i+1根柱子额外受到1 11点伤害。该问题具有单调性——若X XX能使所有柱子倒塌，则任何大于X XX的值也一定能。
算法选择：
- 整数二分：利用"可行性随X XX增大而单调不减"的性质，在值域[ 1 , 10 9 ] [1, 10^9][1,109]上二分查找最小可行X XX
- 模拟验证（check函数）：对于给定的X XX，按照题目规则模拟连锁反应，判断是否能倒塌所有柱子
关键步骤：
- 二分边界：左边界l = 1 l = 1l=1，右边界r = 10 9 r = 10^9r=109（X XX的最大可能值）
- 二分过程：
- 取中点m i d = ⌊ l + r 2 ⌋ mid = \lfloor \frac{l + r}{2} \rfloormid=⌊2l+r⌋
- 调用
check(mid)模拟验证：- 所有柱子先减去X XX：
b[i] = \max(0, A_i - X) - 从左到右传播连锁反应：若b [ i ] = 0 b[i] = 0b[i]=0，则b [ i + 1 ] = max ( 0 , b [ i + 1 ] − 1 ) b[i+1] = \max(0, b[i+1] - 1)b[i+1]=max(0,b[i+1]−1)
- 检查是否所有b [ i ] = 0 b[i] = 0b[i]=0
- 所有柱子先减去X XX：
- 若
check(mid)为真：r = m i d r = midr=mid（尝试更小的X XX） - 若
check(mid)为假：l = m i d + 1 l = mid + 1l=mid+1（需要更大的X XX）
- 输出l ll（最小可行X XX）
时间/空间复杂度：
- 时间复杂度：O ( N log C ) O(N \log C)O(NlogC)，其中C = 10 9 C = 10^9C=109为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]
- 时间复杂度：O ( N log C ) O(N \log C)O(NlogC)，其中C = 10 9 C = 10^9C=109为X XX的值域范围。每次
整数二分的核心思想：
- 单调性利用：若X XX可行，则所有X ′ > X X' > XX′>X也可行，因此可行解集合具有单调性，适合二分
- 验证分离：将"寻找最优解"与"验证可行性"分离，通过高效的模拟验证配合二分快速缩小搜索范围
- 边界处理：使用
max(0, ...)防止耐久度变为负数，避免连锁反应过度传播 - 连锁传播顺序：必须严格从左到右依次判断，因为第i ii根是否倒塌会影响第i + 1 i+1i+1根的状态
- 适用于具有单调性的最优化问题，将求解转化为"判定问题 + 二分搜索"的经典模式
【算法标签】
#整数二分
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;constintN=500005;// 最大柱子数量intn;// 柱子数量inta[N],b[N];// a[i]: 第i根柱子的原始耐久度, b[i]: 模拟时的临时耐久度// 检查：当施加的力为x时，是否能使所有柱子倒塌boolcheck(intx){// 复制原始耐久度到临时数组，避免修改原数组memcpy(b,a,sizeof(a));// 第一步：所有柱子受到直接冲击xfor(inti=1;i<=n;i++)b[i]=max(0,b[i]-x);// 第二步：连锁反应从左到右传播// 如果第i根柱子倒塌（耐久度为0），则第i+1根额外受到1点伤害for(inti=1;i<n;i++){if(b[i]==0)// 第i根柱子倒塌b[i+1]=max(0,b[i+1]-1);// 右侧相邻柱子额外减1（不低于0）}// 检查是否所有柱子都倒塌（耐久度都为0）for(inti=1;i<=n;i++){if(b[i]>0)// 存在未倒塌的柱子returnfalse;}returntrue;// 所有柱子都倒塌}intmain(){cin>>n;// 读入柱子数量// 读入每根柱子的耐久度for(inti=1;i<=n;i++)cin>>a[i];// 二分查找最小的Xintl=1,r=1e9;// X的范围：[1, 1e9]while(l<r){intmid=(l+r)/2;// 取中间值if(check(mid))// mid可行，尝试更小的Xr=mid;else// mid不可行，需要更大的Xl=mid+1;}// 输出最小的Xcout<<l<<endl;return0;}【运行结果】
4 2 3 2 4 3