草原蛇决斗问题的 C++ 实现

以下是使用 C++ 实现该问题的代码： ```cpp #include <iostream> #include <vector> #include <algorithm> // 自定义比较函数，用于对蛇按实力排序 bool compare(const std::pair<int, int>& a, const std::pair<int, int>& b) { if (a.second != b.second) { return a.second > b.second; } return a.first > b.first; } // 模拟决斗过程 int simulateDuel(std::vector<std::pair<int, int>> snakes) { while (snakes.size() > 1) { // 按实力排序 std::sort(snakes.begin(), snakes.end(), compare); int strongest = snakes[0].second; int weakest = snakes.back().second; // 检查最强的蛇吃了最弱的蛇后是否会成为最弱的蛇 bool willBeWeakest = false; if (snakes.size() > 2) { std::vector<std::pair<int, int>> newSnakes = snakes; newSnakes[0].second -= weakest; newSnakes.pop_back(); std::sort(newSnakes.begin(), newSnakes.end(), compare); if (newSnakes.back().second >= newSnakes[0].second) { willBeWeakest = true; } } if (willBeWeakest) { break; } // 最强的蛇选择吃最弱的蛇 snakes[0].second -= weakest; snakes.pop_back(); } return snakes.size(); } int main() { int T; std::cin >> T; std::vector<std::pair<int, int>> snakes; for (int t = 0; t < T; ++t) { if (t == 0) { int n; std::cin >> n; snakes.resize(n); for (int i = 0; i < n; ++i) { snakes[i].first = i + 1; std::cin >> snakes[i].second; } } else { int k; std::cin >> k; for (int i = 0; i < k; ++i) { int x, y; std::cin >> x >> y; snakes[x - 1].second = y; } } int result = simulateDuel(snakes); std::cout << result << std::endl; } return 0; } ``` ### 代码解释： 1. **自定义比较函数 `compare`**：用于对蛇按实力排序，实力强的蛇排在前面。 2. **模拟决斗函数 `simulateDuel`**： - 当蛇的数量大于 1 时，进行决斗。 - 对蛇按实力排序，找出最强和最弱的蛇。 - 检查最强的蛇吃了最弱的蛇后是否会成为最弱的蛇，如果会，则决斗结束。 - 否则，最强的蛇吃了最弱的蛇，更新体力值并移除最弱的蛇。 3. **主函数 `main`**： - 读取数据组数 `T`。 - 对于第一组数据，读取蛇的数量 `n` 和每条蛇的体力值。 - 对于后续数据，读取修改的蛇的数量 `k` 和修改的二元组 `(x, y)`，更新蛇的体力值。 - 调用 `simulateDuel` 函数模拟决斗，并输出结果。 ### 复杂度分析： - 时间复杂度：$O(T * n log n)$，其中 $T$ 是数据组数，$n$ 是蛇的数量。每次模拟决斗需要对蛇进行排序，排序的时间复杂度为 $O(n log n)$。 - 空间复杂度：$O(n)$，主要用于存储蛇的信息。 ######[AI问答 | 925点数解答 | 2026-06-13 21:35:08]