[ARC128E] K Different Values
考察 \(k=2\) 的情形，这个很经典，就是绝对众数。这样的话我们发现显然的一个必要条件是 \(\max A_i \le \lceil \frac{n}{k} \rceil\)。进一步，我们按照 \(k\) 为块长分块，还需满足 \(A_i = \lceil \frac{n}{k} \rceil\) 的个数不超过最后一段的块长。
按照 OIer 的直觉，我们断言这就是充要条件，考虑归纳构造，\(n \le k\) 的情形是平凡的。现在考虑填第一个数，如果 \(A_i = \lceil \frac{n}{k} \rceil\) 的个数刚好等于最后一段块长了，那么就把最小的这样的 \(A_i\) 填进去，否则找还能填的最小的填进去，这时候需要后面满足前 \(k - 1\) 个数不能填 \(i\)，但是按照我们的分块我们必然可以在后面填好 \(i\) 的位置，然后去掉 \(i\) 的限制后按照归纳假设还是有解的，然后就构造完了。做法就按照构造过程每次填数即可，复杂度 \(O(N \sum A_i)\)。
const int N = 2e5 + 10;
int n, m, k;
int a[N], b[N], vis[N];
int main() {
read(n, k);
for(int i = 1; i <= n; ++i)
read(a[i]), m += a[i];
int cnt = 0;
for(int i = 1; i <= n; ++i) {
if(a[i] > (m + k - 1) / k) {
puts("-1");
return 0;
} else if(a[i] == (m + k - 1) / k) {
++cnt;
}
}
if(cnt > (m - 1) % k + 1) {
puts("-1");
return 0;
}
for(int i = m; i >= 1; --i) {
cnt = 0;
for(int j = 1; j <= n; ++j)
if(a[j] == (i + k - 1) / k) ++cnt;
if(i <= m - k) vis[b[m - i + 1 - k]] = 0;
if(cnt == (i - 1) % k + 1) {
for(int j = 1; j <= n; ++j) {
if(a[j] == (i + k - 1) / k && !vis[j]) {
--a[j], vis[j] = 1,
b[m - i + 1] = j;
break;
}
}
} else {
for(int j = 1; j <= n; ++j) {
if(a[j] && !vis[j]) {
--a[j], vis[j] = 1;
b[m - i + 1] = j;
break;
}
}
}
}
for(int i = 1; i <= m; ++i)
printf("%d ",b[i]);
return 0;
}