ABC435C 多米诺
ABC435C 多米诺
【算法标签】 贪心
【语法标签】 :数组、for循环、long long、cin/cout、max/min
数轴上有 个多米诺骨牌排成一列,第 个骨牌位于坐标 ,高度为 。
当第 个骨牌向右倒下时,坐标范围 内的所有骨牌都会跟着向右倒下。
现在第 个骨牌向右倒下。问最终总共有多少个骨牌倒下?
数据范围:
二、解题思路
2.1 理解「多米诺效应」
题目描述的本质就是多米诺骨牌的连锁反应:
- 第 1 个骨牌倒下,砸倒范围 内的骨牌
- 被砸倒的骨牌也会向右倒下,可能砸倒更远处的骨牌
- 连锁反应一直持续,直到没有新的骨牌被砸倒
这就形成了一个区间不断向右扩展的过程。
2.2 核心贪心策略
想象我们维护一个变量 reach,表示当前已经(或将要)倒下的最远位置。
- 初始时,骨牌 1 倒下,最远能砸到位置 ,所以
reach = A_1 - 然后从左往右扫描骨牌 (从 2 到 N):
- 如果
reach:说明骨牌 已经被之前的连锁反应砸倒了,它会继续向右倒下,可能把reach往右推:reach = max(reach, i + A_i - 1) - 如果
reach:说明连锁反应中断了——骨牌 没有倒下,而且它后面的骨牌也都不可能倒下了(因为多米诺效应是从左往右传递的),直接结束扫描
- 如果
- 最终,倒下的骨牌就是位置 到
min(reach, N)的所有骨牌,数量为min(reach, N)。
2.3 为什么是正确的?
关键观察:骨牌只能向右倒下,连锁反应只能从左往右传递。
如果骨牌 没有倒下( reach),那么 右边的所有骨牌也都不可能倒下——因为没有任何倒下的骨牌能"跨过"一个站着的骨牌去砸倒更右边的。
所以只要遇到第一个 reach,后面的就全都不用考虑了。
2.4 手动模拟样例
样例 1:,
初始: reach = A₁ = 3
i=2: 位置2 ≤ reach=3 → 骨牌2倒下
reach = max(3, 2+1-1) = max(3, 2) = 3
i=3: 位置3 ≤ reach=3 → 骨牌3倒下
reach = max(3, 3+4-1) = max(3, 6) = 6
i=4: 位置4 ≤ reach=6 → 骨牌4倒下
reach = max(6, 4+1-1) = max(6, 4) = 6
最终 reach=6, N=4 → 倒下的数量 = min(6, 4) = 4样例 2:,
初始: reach = A₁ = 1
i=2: 位置2 > reach=1 → 连锁中断!
后面的骨牌都不会倒下
最终 reach=1 → 倒下的数量 = min(1, 9) = 1样例 3:,
初始: reach = A₁ = 5
i=2: 位置2 ≤ 5 → reach = max(5, 2+4-1=5) = 5
i=3: 位置3 ≤ 5 → reach = max(5, 3+3-1=5) = 5
i=4: 位置4 ≤ 5 → reach = max(5, 4+2-1=5) = 5
i=5: 位置5 ≤ 5 → reach = max(5, 5+1-1=5) = 5
i=6: 位置6 > 5 → 连锁中断!
最终 reach=5 → 倒下的数量 = min(5, 10) = 5三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int a[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
// reach:当前已经倒下(或即将倒下)的最远位置
long long reach = a[1]; // 第1个骨牌能砸到的最远位置
for (int i = 2; i <= n; i++) {
if (i <= reach) {
// 骨牌i被砸倒了,它继续向右扩展
reach = max(reach, (long long)i + a[i] - 1);
} else {
// 连锁中断
break;
}
}
// 倒下的数量不会超过N
cout << min(reach, (long long)n) << endl;
return 0;
}代码说明
| 行 | 说明 |
|---|---|
reach = a[1] | 初始时骨牌 1 倒下,能砸到的最远位置是 |
i <= reach | 判断骨牌 i 是否在已倒下的范围内 |
i + a[i] - 1 | 骨牌 i 倒下后能砸到的最远坐标 |
max(reach, ...) | 不断向右推进最远距离 |
break | 一旦连锁中断,后面的骨牌都不会倒下 |
min(reach, n) | 最远位置可能超过 N,取 min 得到实际数量 |
注意 long long
,所以 ,用 int 也完全可以。但这里用了 long long 是一个好习惯——当数据范围变大时不至于溢出。
四、复杂度分析
| 阶段 | 复杂度 |
|---|---|
| 读入 | |
| 扫描 | |
| 总 |
空间复杂度:数组 占 。
实际上我们甚至不需要存整个数组——可以在读入的同时处理(边读边判断)。但这个写法可读性更好,且 的数组完全在内存范围内。
五、思维扩展
5.1 如果骨牌可以向左倒呢?
如果每个骨牌可以选择方向倒下,问题就变成了经典的「多米诺骨牌推倒问题」,通常用区间 DP 或贪心解决。
但本题骨牌只能向右倒,简化成了一个单方向扫描的贪心。
5.2 与「跳跃游戏」的相似性
本题的思想和 LeetCode 55「跳跃游戏」非常相似:维护能到达的最远位置,从左往右扫描。这类「维持最远可达」的贪心模式值得记住。
5.3 为什么不用搜索?
高达 ,BFS/DFS 会超时且浪费。贪心扫描一次 就能解决,因为连锁反应有单调性——最远距离只增不减。
六、易错点
忽略 的情况:当 时,范围是 ,即只能砸倒自己,不会扩展。
reach 可能超过 N:最后要用
min(reach, n),否则可能输出比 N 大的数(虽然题目中 的情况下 reach 最多到 ,不算溢出,但逻辑上倒下的数量不可能超过总数 N)。下标从 1 开始:这里骨牌编号和坐标都是 ,用 1-based 下标最自然。
