C++ 实现计算斗地主手牌最少出牌次数：代码、规则与复杂度全解析

以下是一个用 C++ 实现的解决方案，用于计算每组手牌最少需要多少次出牌可以打光。 ```cpp #include <iostream> #include <vector> #include <algorithm> // 定义牌的结构体 struct Card { int num; // 牌的数码 int suit; // 牌的花色 Card(int n, int s) : num(n), suit(s) {} }; // 比较函数，用于对牌进行排序 bool compareCards(const Card& a, const Card& b) { if (a.num != b.num) { if (a.num == 0) return false; // 大小王放最后 if (b.num == 0) return true; if (a.num == 2) return false; // 2 放较后 if (b.num == 2) return true; if (a.num == 1) return false; // A 放较后 if (b.num == 1) return true; return a.num < b.num; } return a.suit < b.suit; } // 计算最少出牌次数 int minMovesToClear(std::vector<Card>& hand) { std::sort(hand.begin(), hand.end(), compareCards); int moves = 0; int i = 0; while (i < hand.size()) { // 处理大小王 if (hand[i].num == 0) { if (i + 1 < hand.size() && hand[i + 1].num == 0) { i += 2; // 大小王一起出 } else { i++; // 单出小王或大王 } moves++; continue; } // 寻找连续相同数码的牌 int j = i; while (j < hand.size() && hand[j].num == hand[i].num) { j++; } moves++; // 出这组相同数码的牌 i = j; } return moves; } int main() { int T, n; std::cin >> T >> n; for (int t = 0; t < T; t++) { std::vector<Card> hand; for (int i = 0; i < n; i++) { int a, b; std::cin >> a >> b; hand.emplace_back(a, b); } int result = minMovesToClear(hand); std::cout << result << std::endl; } return 0; } ``` 代码说明： 1. 结构体 `Card`：用于存储每张牌的数码和花色。 2. 比较函数 `compareCards`：对牌进行排序，大小王放2 和 A 也相对靠后，其余按数码从小到大排序。 3. 函数 `minMovesToClear`： - 首先对牌进行排序。 - 遍历手牌，处理大小王的情况，如果有大小王可以一起出，否则单出。 - 对于其他牌，寻找连续相同数码的牌，将其作为一组出牌。 4. 主函数 `main`： - 读取输入的手牌组数 `T` 和每组手牌的张数 `n`。 - 对于每组手牌，读取每张牌的信息并存储在 `hand` 向量中。 - 调用 `minMovesToClear` 函数计算最少出牌次数并输出结果。 复杂度分析： - 时间复杂度：排序的时间复杂度为 $O(n log n)$，遍历手牌的时间复杂度为 $O(n)$，因此总的时间复杂度为 $O(n log n)$。 - 空间复杂度：主要用于存储手牌，空间复杂度为 $O(n)$。 ######[AI问答 | 894点数解答 | 2026-01-24 22:37:01]