巧判小朋友同桌意愿：满足需求还是无解难题？

```cpp #include <iostream> #include <vector> // 判断是否能让所有小朋友满意的函数 bool canSatisfyAll(const std::vector<int>& p) { int n = p.size() / 2; std::vector<bool> paired(2 * n + 1, false); for (int i = 1; i <= 2 * n; ++i) { if (paired[i]) continue; int want = p[i - 1]; if (want == i || paired[want] || p[want - 1] != i) { return false; } paired[i] = true; paired[want] = true; } return true; } int main() { int n; std::cin >> n; std::vector<int> p(2 * n); for (int i = 0; i < 2 * n; ++i) { std::cin >> p[i]; } if (canSatisfyAll(p)) { std::cout << "Yes" << std::endl; } else { std::cout << "No" << std::endl; } return 0; } ``` 代码解释 1. `canSatisfyAll`函数： - 该函数接受一个存储每个小朋友想和谁做同桌信息的向量`p`作为参数，用于判断是否能让所有小朋友满意。 - 首先，通过`p.size() / 2`得到桌子的数量`n`，并创建一个布尔类型的向量`paired`，其大小为`2 * n + 1`，用于标记每个小朋友是否已经配对。 - 遍历每个小朋友，对于未配对的小朋友`i`，获取其想和谁做同桌的信息`want`。 - 检查`want`是否等于`i`（即自己想和自己做同桌）、`want`是否已经配对、以及`want`想和做同桌的人是否是`i`，若不满足条件则返回`false`。 - 若满足条件，则将`i`和`want`标记为已配对。 - 若所有小朋友都能成功配对，则返回`true`。 2. `main`函数： - 首先读取桌子的数量`n`。 - 然后读取每个小朋友想和谁做同桌的信息，存储在向量`p`中。 - 调用`canSatisfyAll`函数进行判断，根据返回值输出`Yes`或`No`。 ######[AI问答 | 599点数解答 | 2025-11-16 20:06:12]