乌拉乎餐厅排队难题：代码详解最少卡片修改次数

```cpp #include <iostream> #include <vector> #include <algorithm> // 此函数用于计算最少需要修改的卡片数量 int minCardChanges(const std::vector<int>& cards) { int n = cards.size(); // 初始化最小修改次数为一个较大的值 int minChanges = n; // 枚举分割点，尝试将队伍分成两部分 for (int split = 0; split <= n; ++split) { int changes = 0; // 统计前半部分需要修改为1的数量 for (int i = 0; i < split; ++i) { if (cards[i] != 1) { changes++; } } // 统计后半部分需要修改为2的数量 for (int i = split; i < n; ++i) { if (cards[i] != 2) { changes++; } } // 更新最小修改次数 minChanges = std::min(minChanges, changes); } return minChanges; } int main() { int n; // 读取客人的数量 std::cin >> n; std::vector<int> cards(n); // 读取每个客人的用餐批次 for (int i = 0; i < n; ++i) { std::cin >> cards[i]; } // 计算最少修改次数 int result = minCardChanges(cards); // 输出结果 std::cout << result << std::endl; return 0; } ``` 代码解释 1. `minCardChanges` 函数： - 通过枚举所有可能的分割点，将队伍分成前半部分和后半部分。 - 对于每个分割点，统计前半部分需要修改为 `1` 的客人数量和后半部分需要修改为 `2` 的客人数量。 - 比较所有分割点下的修改数量，找出最小值。 2. `main` 函数： - 读取客人的数量 `n`。 - 读取每个客人的用餐批次并存储在 `cards` 向量中。 - 调用 `minCardChanges` 函数计算最少修改次数。 - 输出最终结果。 这个算法通过枚举所有可能的分割点，保证了能找到让编号符合设想所需的最少修改次数。时间复杂度是 $O(n^2)$，因为有一个外层循环枚举分割点，内层有两个循环统计修改次数。 ######[AI问答 | 583点数解答 | 2026-02-08 19:38:03]