简单无向图的可视化，根据 Erdős–Gallai 定理将度数序列
\(d\) 排序可得，若满足
\[
\forall k\in[1,n],\sum_{i=1}^kd_k\le
k\times(k-1)+\sum_{i=k+1}^n\min(k,d_i)
\] 且
\[
\sum_{i=1}^nd_i\equiv0\ mod\ 2
\]
则序列可图，感性理解就是我们不断满足构成部分完全图的上界
稍加分析我们也可以发现，最后的答案是一个连续的序列简单证明就是若
\(d_n=i\) 和 \(d_n=j\)
都是可图的，那么我们可以删去两边增加一条边的方法递推得到中间的合法值
所以这道题再套上一个二分即可
二分是二分一个区间的左右端点，因此我们需要分清什么时候偏大，什么时候偏小
若 \(i\) 时不满足条件，当 \(mid\ge d_i\) 时，\(mid\) 偏大，否则偏小
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
| #include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
using namespace std;
typedef long long int64;
inline int read(int f = 1, int x = 0, char ch = ' ')
{
while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
return f*x;
}
const int N = 5e5+5;
int n, p, ansl, ansr, b[N], tax[N], a[N], l, r; int64 s[N];
int valid(int mid)
{
for(int i = 0; i < n; ++i) tax[i] = 0; ++tax[mid];
for(int i = 1; i < n; ++i) ++tax[b[i]];
for(int i = n-1, j = 0; ~i; --i)
for(int k = 1; k <= tax[i]; ++k)
a[++j] = i;
for(int i = 1; i <= n; ++i) s[i] = s[i-1]+a[i];
for(int i = 1, j = n+1; i < n; ++i)
{
for(j = max(i+1, j); j > i+1&&a[j-1] <= i; --j);
if(s[i] > (j-1ll-i)*i+s[n]-s[j-1]+i*(i-1ll)) return a[i]<=mid?-1:1;
}
return 0;
}
int main()
{
n = read()+1; for(int i = 1; i < n; ++i) b[i] = read(), p ^= b[i]&1;
l = 0, r = (n-1-p)>>1, ansr = -1;
while(l <= r)
{
int mid = (l+r)>>1;
if(valid(mid<<1|p) == -1) r = mid-1;
else l = mid+1, ansr = mid;
}
l = 0, r = (n-1-p)>>1, ansl = -1;
while(l <= r)
{
int mid = (l+r)>>1;
if(valid(mid<<1|p) == 1) l = mid+1;
else r = mid-1, ansl = mid;
}
if(ansl > ansr||ansl == -1||ansr == -1) return puts("-1"), 0;
for(int i = ansl; i <= ansr; ++i) printf("%d ", i<<1|p); puts("");
return 0;
}
|