BZOJ5249 [多省联考2018] IIIDX

2018 年 04 月 8 日发布.

Description

给定一个长为 $n$ 的序列 $d$ （可能有重复）和一个常数 $k$ （不一定是整数）。求 $d$ 的一个排列，要求满足 $d_i \geqslant d_{\lfloor\frac ik\rfloor}$ 。

求所有满足条件的排列中字典序最大的一个。

Solution

首先，字典序最小的一个就是直接排序一遍（然而没什么用）。

贪心方法...算了我还是直接说正解好了。

假设我们有一个函数叫做 check ，能够在我填完前面一部分的时候告诉我是否存在合法解。

容易证明从前往后填到某一位的时候这一位填的越小越容易有解，所以可以逐位二分。

时间复杂度 $O(n\log n * Check)$ 。

先考虑一个 $O(n)$ 的 check 怎么写。

显然 $1$ 到 $n$ 的顺序同时也是这棵树的 bfs 序，所以不存在一个点填了而它的父亲没填的情况。

考虑把所有填了的点（带着它的子树）从它的父亲上摘下来。

如果现在填了 $k$ 个数，那么就有 $k$ 棵树组成的森林。

可以发现，如果我给每棵树分配一些权值，使得每棵树里分配的权值都不小于这棵树的树根权值，并且个数恰好是这棵树里除根结点外的结点个数，那么我一定能够找到一种合法的方案，即每棵树按 bfs 序从小到大填即可。

所以说我现在相当于有 $k$ 个盒子，第 $i$ 个盒子有一个最小权值 $t_i$ 和一个大小 $s_i$ ，现在我要将剩余 $n-k$ 个数放到这些盒子里，问是否存在合法方案。

那么根据贪心策略我只需要把盒子按 $t_i$ 排序，然后把 $n-k$ 个数从小到大放到盒子里即可。

这样就可以拿到 60 分（配合贪心有 70 ）的好成绩啦！

然后再来考虑如何把 check 加快。

我们令 $b_i$ 表示 i 这个数出现的次数，那么 check 返回 true 当且仅当

对于所有的 $x$ ，都有 $\sum_{i \ge x} b_i \ge \sum_{t_i \ge x} s_i$ 。

把不等式移项，可以得到它是一个后缀和大于零的形式。线段树维护最小后缀和，判断其是否非负即可。

总复杂度 $O(n\log^2n)$

Code

#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>

inline int readInt() {
  int ans = 0, c;
  while (!isdigit(c = getchar()));
  do ans = ans * 10 + c - '0';
  while (isdigit(c = getchar()));
  return ans;
}

const int N = 530000;
const int L = N * 20;

char s[L], *p = s;

void print(int x) {
  if (x == 0) return;
  print(x / 10);
  *(p++) = x % 10 + '0';
}

int n, m, A[N], B[N], C[N];
int siz[N], val[N];
double k;

inline int fa(int x) { return (int)(floor(x / k + 1e-5)); }

int len;
int sumv[N * 4], minv[N * 4];

inline void upd(int o) {
  sumv[o] = sumv[o << 1] + sumv[o << 1 | 1];
  minv[o] = std::min(minv[o << 1 | 1], minv[o << 1] + sumv[o << 1 | 1]);
}

void build() {
  for (int i = 0; i < len; ++i) minv[i + len] = sumv[i + len] = B[i + 1];
  for (int i = len - 1; i > 0; --i) upd(i);
}

void add(int x, int y) {
  int t = B[x] -= y;
  x += len - 1;
  sumv[x] = minv[x] = t;
  for (x >>= 1; x > 0; x >>= 1) upd(x);
}

inline bool check() { return minv[1] >= 0; }
inline bool check(int x, int y) {
  add(y, siz[x]);
  bool ans = check();
  add(y, -siz[x]);
  return ans;
}

int main() {
  n = readInt();
  scanf("%lf", &k);
  for (int i = 0; i < n; ++i) A[i] = readInt();
  std::sort(A, A + n);

  for (int i = 0; i < n; ++i) {
    ++B[(i != 0 && A[i] == A[i - 1]) ? m : ++m];
    C[m] = A[i];
  }

  len = 1;
  while (len < m) len <<= 1;
  build();
  for (int i = n; i > 0; --i)
    siz[fa(i)] += ++siz[i];
  add(val[0] = 1, n);
  for (int i = 1; i <= n; ++i) {
    int s = siz[i];
    add(val[fa(i)], -s);
    int l = val[fa(i)], r = m;
    while (l < r) {
      int mid = (l + r + 1) >> 1;
      if (check(i, mid)) l = mid;
      else r = mid - 1;
    }
    add(val[i] = l, s);
  }
  for (int i = 1; i <= n; ++i) {
    print(C[val[i]]);
    *(p++) = ' ';
  }
  *(p++) = '\0';
  puts(s);
  return 0;
}