德州扑克比赛筹码分配难题：代码实现与复杂度剖析

```cpp #include <iostream> #include <vector> #include <algorithm> #include <climits> using namespace std; // 定义选手结构体，包含筹码量、牌力和最终筹码量 struct Player { int chips; int strength; double finalChips; }; int main() { int n; cin >> n; vector<Player> players(n); // 读取每位选手的初始筹码量 for (int i = 0; i < n; ++i) { cin >> players[i].chips; players[i].finalChips = 0; } // 读取每位选手的牌力 for (int i = 0; i < n; ++i) { cin >> players[i].strength; } while (true) { int nonZeroCount = 0; int minChips = INT_MAX; // 统计非零筹码选手数量和最小筹码量 for (const auto& player : players) { if (player.chips > 0) { ++nonZeroCount; minChips = min(minChips, player.chips); } } // 如果非零筹码选手数量小于等于1，结束循环 if (nonZeroCount <= 1) { break; } int sidePot = 0; vector<int> contributors; // 建立边池，扣除每位选手的最小筹码量 for (int i = 0; i < n; ++i) { if (players[i].chips > 0) { sidePot += minChips; players[i].chips -= minChips; contributors.push_back(i); } } int maxStrength = INT_MIN; vector<int> winners; // 找出向边池提供筹码的选手中牌力最大的 for (int index : contributors) { if (players[index].strength > maxStrength) { maxStrength = players[index].strength; winners.clear(); winners.push_back(index); } else if (players[index].strength == maxStrength) { winners.push_back(index); } } // 均分边池的筹码 double share = static_cast<double>(sidePot) / winners.size(); for (int index : winners) { players[index].finalChips += share; } } // 处理最后可能剩余筹码的选手 for (int i = 0; i < n; ++i) { players[i].finalChips += players[i].chips; } // 输出每位选手的最终筹码量 for (const auto& player : players) { cout.precision(12); cout << player.finalChips << endl; } return 0; } ``` 代码解释： 1. 结构体 `Player`：用于存储每位选手的筹码量、牌力和最终筹码量。 2. 输入处理：读取选手数量、每位选手的初始筹码量和牌力。 3. 边池构建循环：在循环中，统计非零筹码选手数量和最小筹码量。如果非零筹码选手数量小于等于1，结束循环。否则，建立边池，扣除每位选手的最小筹码量，并找出向边池提供筹码的选手中牌力最大的，将边池筹码均分给这些选手。 4. 最终处理：处理最后可能剩余筹码的选手，并将其加到最终筹码量中。 5. 输出结果：输出每位选手的最终筹码量。 复杂度分析： - 时间复杂度：$O(n^2)$，其中 $n$ 是选手的数量。在最坏情况下，每次循环都需要遍历所有选手。 - 空间复杂度：$O(n)$，主要用于存储选手信息和边池相关信息。 ######[AI问答 | 907点数解答 | 2025-06-02 15:24:00]