B3964 [语言月赛 202404] 天上的气球 题解
Maxmilite
·
·
题解
Source & Knowledge
2024 年 4 月语言月赛，由洛谷网校入门计划/基础计划提供。
题目大意
求解从每个位置向上看，能看到的气球的颜色分别是什么。
## 题目分析
本题仍然可以使用擂台法解决，但是需要做一定的修改。使用两个 $n \times m$ 的二维数组 $H, C$。$H$ 是擂台，$C$ 是当前处在擂台中气球的颜色。
每次读入气球 $x_i, y_i, h_i, c_i$。需要将 $h_i$ 与 $H_{x_i, y_i}$ 比较。如果 $h_i$ 更小，则更新 $H_{x_i, y_i} = h_i, C_{x_i, y_i} = c_i$。最终输出 $C$ 数组即可。
```cpp
int H[1005][1005], C[1005][1005];
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
H[i][j] = 1000000001; // 小擂台初始时要很大
}
}
...
for (int i = 1; i <= k; ++i) {
int x, y, h, c;
cin >> x >> y >> h >> c;
if (h < H[x][y]) {
H[x][y] = h;
C[x][y] = c;
}
}
// 输出
```
## 视频讲解
