[Gym102538B] Best Tree

做法

容易证明,对于一个长度为 \(n\) 的度数序列 \(d\),存在一棵对应的 \(n\) 个点的树的充要条件是 \(1 \le d_i < n\)\(\sum {d_i} = 2(n-1)\)(从叶子归纳)。

考虑去钦定这个树的 \(k\) 个匹配,如果能钦定出来就说明答案 \(\ge k\)。钦定两个点匹配可以看作这两个点被缩到了一起,变成了一个度数和为两个点的度数之和减去 \(2\) 的点。只要保证所有匹配缩起来之后得到的度数序列依然满足之前所说的条件即可。这是一个众所周知的贪心问题,排序后贪心用小的匹配大的即可。需要特别注意 \(1\)\(1\) 在点数大于 \(2\) 时不能匹配(因为 \(1+1-2=0\)),但是点数等于 \(2\) 时可以匹配。

代码

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
#include <bits/stdc++.h>

using namespace std;

const int maxn = 200010;

int T, n, d[maxn];

int main() {
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &d[i]);
if (n == 2) {
puts("1");
continue;
}
multiset<int> st;
int ans = 0;
for (int i = 1; i <= n; i++) st.insert(d[i]);
while (st.size() >= 2) {
int x = * st.begin(), y = * st.rbegin();
if (x + y - 2 >= n) {
set<int>::iterator _ = st.end();
st.erase(-- _);
continue;
}
if (x + y - 2 <= 0) break;
set<int>::iterator _ = st.end();
st.erase(-- _);
st.erase(st.begin());
++ ans;
}
printf("%d\n", ans);
}
return 0;
}