高效模拟与排序：N个动态数组的批量插入与升序输出实现

这是一个典型的**模拟 + 排序**问题，核心在于： - 维护 `N` 个动态数组（可变长）； - 每次操作向第 `X` 个数组添加一个整数 `Y`； - 最终对每个数组**排序后输出：长度 + 所有元素（升序）**。 --- ### ✅ 解题思路 1. **数据结构选择**： - 使用 `vector<vector<long long>> arrays(N + 1)`（下标从 1 开始），避免频繁 realloc，也便于后续排序。 - 注意：`Y ≤ 10^9`，所以用 `long long` 或 `int` 均可（题目没说负数，但 `int` 足够，不过为保险推荐 `long long` 或直接 `int` —— 因为 `10^9 < 2^31`，`int` 在大多数系统中是 32 位，安全）。 2. **输入处理**： - 读入 `N`, `M`； - 循环 `M` 次，每次读 `X`, `Y`，执行 `arrays[X].push_back(Y)`。 3. **输出处理**： - 对每个 `i` 从 `1` 到 `N`： - `sort(arrays[i].begin(), arrays[i].end())` - 输出 `arrays[i].size()`，然后输出所有元素（空格分隔） 4. **性能注意**： - `M ≤ 300000`，最坏情况所有插入都在一个数组 → 该数组要排序 300000 个数，`O(M log M)` 可接受（`3e5 * log2(3e5) ≈ 3e5 * 19 ≈ 5.7e6` 次操作，很快）。 - 总体时间复杂度：`O(M + Σ|arr[i]| log |arr[i]|) ≤ O(M log M)`，满足要求。 --- ### ✅ C++ 代码实现（高效、简洁、AC-ready） ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, M; cin >> N >> M; // 创建 N+1 个 vector（索引 1~N 使用） vector<vector<int>> arrays(N + 1); for (int i = 0; i < M; ++i) { int X, Y; cin >> X >> Y; arrays[X].push_back(Y); } // 输出每个数组：大小 + 排序后元素 for (int i = 1; i <= N; ++i) { auto& arr = arrays[i]; sort(arr.begin(), arr.end()); cout << arr.size(); for (int x : arr) { cout << ' ' << x; } cout << '\n'; } return 0; } ``` --- ### 🧪 样例验证 输入： ``` 3 5 1 3 1 2 1 1 2 1 3 1 ``` 内部状态： - `arrays[1] = {3,2,1}` → sorted → `{1,2,3}` → output: `3 1 2 3` - `arrays[2] = {1}` → `1 1` - `arrays[3] = {1}` → `1 1` ✅ 完全匹配样例输出。 --- ### 💡 进阶优化（可选） - 若内存紧张，可考虑用 `reserve()` 预估大小（例如按平均 `M/N` reserve），减少 `push_back` 的扩容次数。 - 若需去重，题目未要求，不加。 - 若 `Y` 范围极大但重复多，可考虑 `map`/`unordered_map` 计数 + 离散化，但本题只需排序输出全部值，无需。 --- ### 📌 注意事项（开发建议） - 使用 `ios::sync_with_stdio(false); cin.tie(nullptr);` 加速输入（尤其 `M` 达 30 万）。 - 不要用 `endl`（会 flush），用 `'\n'`。 - 数组下标从 `1` 开始，别越界（定义 `N+1` 大小）。 - `vector` 的 `size()` 返回 `size_t`，但输出为整数无妨；若编译警告，可强转 `(int)arr.size()`，但非必须。 --- ######[AI写代码神器 | 1058点数解答 | 2026-03-23 17:49:46]