自动搬运

查看原文

来自洛谷，原作者为

	Maxmilite **

搬运于2025-08-24 21:16:14，当前版本为作者最后更新于2024-04-24 09:16:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Source & Knowledge

2024 年 4 月语言月赛，由洛谷网校入门计划/基础计划提供。

题目大意

$n$ 行 $m$ 列的草原。有 $k$ 个气球。第 $i$ 个气球，位置在第 $x_i$ 行第 $y_i$ 列上空，距离地面高度 $h_i$，气球的颜色为 $c_i$。

求解从每个位置向上看，能看到的气球的颜色分别是什么。

题目分析

本题仍然可以使用擂台法解决，但是需要做一定的修改。使用两个 $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$ 数组即可。

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;
  }
}

// 输出

视频讲解