_rqy's Blog

一只猫猫,想成为天才少女数学家!

0%

BZOJ5249 [多省联考2018] IIIDX

Description

给定一个长为 nn 的序列 dd (可能有重复)和一个常数 kk (不一定是整数)。 求 dd 的一个排列,要求满足 didikd_i \geqslant d_{\lfloor\frac ik\rfloor}

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

Solution

首先,字典序最小的一个就是直接排序一遍(然而没什么用)。

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

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

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

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

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

显然 11nn 的顺序同时也是这棵树的 bfs 序,所以不存在一个点填了而它的父亲没填的情况。

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

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

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

所以说我现在相当于有 kk 个盒子,第 ii 个盒子有一个最小权值 tit_i 和一个大小 sis_i ,现在我要将剩余 nkn-k 个数放到这些盒子里,问是否存在合法方案。

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

这样就可以拿到 60 分(配合贪心有 70 )的好成绩啦!

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

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

对于所有的 xx ,都有 ixbitixsi\sum_{i \ge x} b_i \ge \sum_{t_i \ge x} s_i

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

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

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#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;
}