[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;
}