为了避免餐厅过分拥挤，乌拉乎要求客人们分2批就餐。每天晚饭前，客人们都会在餐厅前排队入内，按乌拉乎的设想，所有第2批就餐的客人排在队尾，队伍的前半部分则由设定为第1批就餐的客人占据。由于客人们不理解乌拉乎的安排，晚饭前的排队成了一个大麻烦。 第i头客人有一张标明她用餐批次D_i(1 <= D_i <= 2)的卡片。虽然所有N头客人排成了很整齐的队伍，但谁都看得出来，卡片上的号码是完全杂乱无章的。 在若干次混乱的重新排队后，乌拉乎找到了一种简单些的方法：客人们不动，他沿着队伍从头到尾走一遍，把那些他认为排错队的客人卡片上的编号改掉，最终得到一个他想要的每个组中的客人都站在一起的队列，例如112222或111122。有的时候，乌拉乎会把整个队列弄得只有1组客人（比方说，1111或222）。 他想知道，如果他想达到目的，那么他最少得改多少头客人卡片上的编号。所有客人在乌拉乎改卡片编号的时候，都不会挪位置。 输入格式 第1行: 1个整数：N * 第2..N+1行: 第i+1行是1个整数，为第i头客人的用餐批次D_i 输出格式 一行: 输出1个整数，为乌拉乎最少要改几头客人卡片上的编号，才能

```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)$，因为有一个外层循环枚举分割点，内层有两个循环统计修改次数。 [2026-02-08 19:38:03 | AI问答 | 583点数解答]