【提高】Comfortable Cows 显示标签 时间限制：C/C++ 1000MS，其他语言 2000MS 内存限制：C/C++ 128MB，其他语言 256MB 难度：提高 分数：100 OI排行榜得分：18(0.1*分数+2*难度) 出题人： 描述 Farmer Nhoj 的草地可以被看作是一个由正方形方格组成的巨大的二维方阵（想象一个巨大的棋盘）。初始时，草地上是空的。 Farmer Nhoj 将会逐一地将 NN（1≤N≤105）头奶牛加入到草地上。第 ii 头奶牛将会占据方格 (xi,yi)，不同于所有已经被其他奶牛占据的方格（0≤xi,yi≤1000）。 一头奶牛被称为是「舒适的」，如果它水平或竖直方向上与恰好三头其他奶牛相邻。然而，太舒适的奶牛往往产奶量落后，所以 Farmer Nhoj 想要额外加入一些奶牛直到没有奶牛（包括新加入的奶牛）是舒适的。注意加入的奶牛的 xx 和 yy 坐标并不一定需要在范围 0…1000内。 对于 1…N 中的每个 i，输出当初始时草地上有奶牛 1…i 时，Farmer Nhoj 为使得没有奶牛舒适，需要加入的奶牛的最小数量。

```cpp #include <iostream> #include <vector> #include <set> using namespace std; // 检查一个点是否有奶牛 bool hasCow(int x, int y, set<pair<int, int>>& cows) { return cows.find({x, y}) != cows.end(); } // 检查一头奶牛是否舒适 bool isComfortable(int x, int y, set<pair<int, int>>& cows) { int count = 0; if (hasCow(x - 1, y, cows)) count++; if (hasCow(x + 1, y, cows)) count++; if (hasCow(x, y - 1, cows)) count++; if (hasCow(x, y + 1, cows)) count++; return count == 3; } // 检查一个点周围是否有舒适的奶牛 bool hasComfortableAround(int x, int y, set<pair<int, int>>& cows) { if (hasCow(x, y, cows) && isComfortable(x, y, cows)) return true; if (hasCow(x - 1, y, cows) && isComfortable(x - 1, y, cows)) return true; if (hasCow(x + 1, y, cows) && isComfortable(x + 1, y, cows)) return true; if (hasCow(x, y - 1, cows) && isComfortable(x, y - 1, cows)) return true; if (hasCow(x, y + 1, cows) && isComfortable(x, y + 1, cows)) return true; return false; } int main() { int N; cin >> N; set<pair<int, int>> cows; int total = 0; for (int i = 0; i < N; i++) { int x, y; cin >> x >> y; cows.insert({x, y}); // 如果新加入奶牛后周围出现舒适的奶牛 if (hasComfortableAround(x, y, cows)) { // 找到需要添加的位置 vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; for (auto& dir : directions) { int newX = x + dir.first; int newY = y + dir.second; if (!hasCow(newX, newY, cows) && hasComfortableAround(newX, newY, cows)) { total++; cows.insert({newX, newY}); } } } cout << total << endl; } return 0; } ``` 代码解释 1. 数据结构：使用 `set<pair<int, int>> cows` 存储奶牛的坐标，借助 `set` 的特性可以高效地判断某坐标是否有奶牛。 2. 辅助函数： - `hasCow` 函数用于检查给定坐标处是否有奶牛。 - `isComfortable` 函数用于判断一头奶牛是否舒适，即其水平或竖直方向上与恰好三头其他奶牛相邻。 - `hasComfortableAround` 函数用于检查某个点周围是否有舒适的奶牛。 3. 主逻辑： - 循环 `N` 次，每次读取一头新奶牛的坐标并插入 `cows` 集合。 - 检查新加入奶牛后其周围是否有舒适的奶牛，若有则找到需要添加奶牛的位置，将其加入 `cows` 集合并更新 `total`。 - 输出当前需要添加的奶牛总数。 复杂度分析 - 时间复杂度：每次插入新奶牛后检查和添加新奶牛的操作时间复杂度为 $O(1)$，总共插入 $N$ 头奶牛，因此总的时间复杂度为 $O(N)$。 - 空间复杂度：使用了 `set` 存储奶牛坐标，最多存储 $N$ 头奶牛，因此空间复杂度为 $O(N)$。 [2026-02-02 17:26:13 | AI问答 | 956点数解答]