你眼中倒映的世界 一瞬永远 —— 《梦语》
分析
首先答案有单调性，考虑二分。
然后每次留下来的构成一颗三叉树，父亲是儿子的中位数，考虑树形 dp。
上很经典的中位数套路，设二分的值为 v，≥v 的 gv 为 1，<v 的 gv为 −1。
如果儿子的值之和 >0 那么父亲就 ≥v。
考虑设 fu 为 gu>0 时最小的子树的叶子中 ≥v 的个数。
转移为 fu=∑fv−maxfv，因为如果 gu>0 必须有两个及以上的 gv=1，多了没用所以是选择最小的的两个 fv。
如果 froot≤ 序列中 ≤v 的个数就是可行的。
代码
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
| const int N = 200005;
int d[N],p[N],f[N];
vector<int> g[N];
int root;
int n,m;
void dfs(int u){
int maxx = 0;
for(int v:g[u]){
dfs(v);
f[u] += f[v];
maxx = max(maxx,f[v]);
}
f[u] -= maxx;
}
bool check(int v){
for(int k=1;k<=root;k++)
f[k] = 0;
for(int k=1;k<=n;k++){
if(p[k])
f[k] = d[p[k]]>=v?0:N+1;
else
f[k] = 1;
}
int cnt = 0;
for(int k=m+1;k<=n;k++)
cnt += d[k]>=v;
dfs(root);
return f[root]<=cnt;
}
int main(){
n = in,m = in;
queue<int> q;
for(int k=1;k<=n;k++)
q.push(k);
root = n;
while(q.size()>1){
int a = q.front();
q.pop();
int b = q.front();
q.pop();
int c = q.front();
q.pop();
root++;
g[root].push_back(a);
g[root].push_back(b);
g[root].push_back(c);
q.push(root);
}
for(int k=1;k<=m;k++)
d[k] = in,p[(int)in] = k;
for(int k=m+1;k<=n;k++)
d[k] = in;
int L = 1,R = 1000000000,ans;
while(L<=R){
int mid = (L+R)>>1;
if(check(mid)){
ans = mid;
L = mid+1;
}
else
R = mid-1;
}
out(ans,'\n');
return 0;
}
|