Description
你有 \(n\) 个有颜色的立方体，第 \(i\) 个立方体的颜色为 \(a_i\)。
你需要将所有立方体分配到若干个架子上。总共有 \(m\) 个架子，第 \(i\) 个架子可以放 \(s_i\) 个立方体。同时，满足 \(s_1 + s_2 + \ldots + s_m = n\)。
假设某个容量为 \(k\) 的架子上，依次放置了颜色为 \(c_1, c_2, \ldots, c_k\) 的立方体。我们定义该架子的“多彩度”为架子上相同颜色的两个立方体之间的最小距离。如果架子上的所有立方体颜色都不同，则多彩度被认为等于架子的容量 \(k\)。
更正式地，\(c_1, c_2, \ldots, c_k\) 的多彩度定义如下：
- 如果 \(c_1, c_2, \ldots, c_k\) 的颜色都不同，则多彩度为 \(k\)。
- 否则，多彩度为最小的整数 \(x \geq 1\)，使得存在下标 \(i\) \((1 \leq i \leq k - x)\) 满足 \(c_i = c_{i+x}\)。
对于每个架子，给定了最小要求的多彩度，即给定了 \(d_1, d_2, \ldots, d_m\)，表示第 \(i\) 个架子的多彩度必须 \(\geq d_i\)。
请你将所有立方体分配到各个架子上，使得每个架子的多彩度都满足要求，或者报告无法做到。
\(1\leq n,m\leq 2\times 10^5\)。
Solution
对于架子 \(i\) 先分 \(\left\lfloor\frac{s_i}{d_i}\right\rfloor\) 个大小为 \(d_i\) 的块和一个大小为 \(s_i\bmod d_i\) 的块，容易发现每个块内的元素不能相同。
然后经过手玩会发现只要满足每个块内元素不相同就一定能构造。证明就考虑对于一个给定的颜色方案，求出其可能的最大的多彩度。
设 \(n\) 为元素总数，\(mx\) 为众数出现次数，\(cnt_i\) 表示出现次数为 \(i\) 的颜色数量。对于出现次数为 \(mx\) 的一定是分 \(mx\) 组，每组的排列顺序相同。然后让出现次数 \([1,mx-1]\) 内的数去填 \(mx-1\) 个间隔，所以多彩度的理论最大值是 \(cnt_{mx}+\frac{n-mx\cdot cnt_{mx}}{mx-1}=\frac{n-cnt_{mx}}{mx-1}\)。构造考虑按照出现次数从大到小依次放到间隔中，且第 \(i\) 个插入的颜色需要接着第 \(i-1\) 个颜色的末尾往后加。
由于 \(cnt_{mx}\leq s_i\bmod d_i\)，所以 \(\frac{s_i-cnt_{mx}}{mx-1}\geq d_i\)，也就一定能构造。
对于把颜色放到架子上，由于所有架子的块互相独立，所以维护一个优先队列表示每个块的长度，然后每次选择当前出现次数最多的块加入当前颜色即可。
把每个架子的每种颜色出现次数求出来后按照证明中的构造即可。
时间复杂度：\(O((n+m)\log n)\)。
Code
#include <bits/stdc++.h>// #define int int64_tconst int kMaxN = 2e5 + 5;int n, m;
int a[kMaxN], cnt[kMaxN], sz[kMaxN], d[kMaxN];
std::vector<int> vec[kMaxN];void dickdreamer() {std::cin >> n >> m;std::fill_n(cnt + 1, n, 0);for (int i = 1; i <= m; ++i) vec[i].clear();std::priority_queue<std::pair<int, int>> q;for (int i = 1; i <= n; ++i) std::cin >> a[i], ++cnt[a[i]];for (int i = 1; i <= m; ++i) std::cin >> sz[i];for (int i = 1; i <= m; ++i) {std::cin >> d[i];for (int j = 1; j <= sz[i] / d[i]; ++j) q.emplace(d[i], i);if (sz[i] % d[i]) q.emplace(sz[i] % d[i], i);}for (int i = 1; i <= n; ++i) {std::vector<std::pair<int, int>> vv;for (int j = 1; j <= cnt[i]; ++j) {if (!q.size()) return void(std::cout << "-1\n");auto [l, id] = q.top(); q.pop();--l, vec[id].emplace_back(i);if (l) vv.emplace_back(l, id);}for (auto p : vv) q.emplace(p);}for (int i = 1; i <= m; ++i) {static int cnt[kMaxN] = {0};std::vector<int> col;for (auto x : vec[i]) {if (!cnt[x]++) col.emplace_back(x);}std::sort(col.begin(), col.end(), [&] (int i, int j) { return cnt[i] > cnt[j]; });std::vector<std::vector<int>> res(cnt[col[0]]);int now = 0;for (auto x : col) {int lim = (cnt[x] == res.size() ? res.size() : res.size() - 1);for (int c = 1; c <= cnt[x]; ++c, now = (now + 1) % lim) {assert(now < res.size());res[now].emplace_back(x);}}for (auto &vec : res) {for (auto x : vec) std::cout << x << ' ';}std::cout << '\n';for (auto x : vec[i]) --cnt[x];}
}int32_t main() {
#ifdef ORZXKRfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifstd::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);int T = 1;std::cin >> T;while (T--) dickdreamer();// std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";return 0;
}