链接
点击跳转
题解
我也不是很懂…抄的题解
Erdős–Gallai定理：
降序序列
{
d
i
}
\{d_i\}
{di}可图的一个充要条件为：
∀
k
∈
[
1
,
n
]
,
∑
i
=
1
k
d
i
≤
[
k
(
k
−
1
)
+
∑
i
=
1
n
m
i
n
(
d
i
,
k
)
]
\forall k \in [1,n], \sum_{i=1}^kd_i \leq \left [ k(k-1) + \sum_{i=1}^n min(d_i,k) \right ]
∀k∈[1,n],i=1∑kdi≤[k(k−1)+i=1∑nmin(di,k)]
然后题解又说满足条件的度数肯定是连续的一段（间隔2），这个也不是很懂
题解还说判断一个度大了还是小了，可以通过不等式不成立的时候
d
n
+
1
d_{n+1}
dn+1在等式的哪边
二分一下好像就可以了
代码
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define iinf 0x3f3f3f3f
#define linf (1ll<<60)
#define eps 1e-8
#define maxn 1000010
#define maxe 1000010
#define cl(x) memset(x,0,sizeof(x))
#define rep(_,__) for(_=1;_<=(__);_++)
#define em(x) emplace(x)
#define emb(x) emplace_back(x)
#define emf(x) emplace_front(x)
#define fi first
#define se second
#define de(x) cerr<<#x<<" = "<<x<<endl
using namespace std
;
using namespace __gnu_pbds
;
typedef long long ll
;
typedef pair
<int,int> pii
;
typedef pair
<ll
,ll
> pll
;
ll
read(ll x
=0)
{
ll c
, f(1);
for(c
=getchar();!isdigit(c
);c
=getchar())if(c
=='-')f
=-f
;
for(;isdigit(c
);c
=getchar())x
=x
*10+c
-0x30;
return f
*x
;
}
ll pre
[maxn
], suf
[maxn
], n
, d
[maxn
], tmp
[maxn
];
#define too_big -1
#define too_small 1
#define ok 0
ll
check(ll v
)
{
ll i
, p
, k
, pos
, s
=0;
rep(i
,n
)tmp
[i
]=d
[i
];
tmp
[n
+1]=v
;
sort(tmp
+1,tmp
+n
+2,greater
<ll
>());
rep(i
,n
+1)pre
[i
]=pre
[i
-1]+tmp
[i
];
for(i
=1;tmp
[i
]!=v
;i
++);pos
=i
;
p
=n
+1;
for(k
=1;k
<=n
+1;k
++)
{
while(p
>k
and tmp
[p
]<k
)s
+=tmp
[p
--];
while(p
<k
)s
-=tmp
[++p
];
if(pre
[k
]>k
*(k
-1)+s
+(p
-k
)*k
)
{
if(k
>=pos
)return too_big
;
else return too_small
;
}
}
return ok
;
}
int main()
{
ll i
, L
, R
, l
, r
, mid
, t
=0;
n
=read();
rep(i
,n
)d
[i
]=read(), t
+=d
[i
]; t
=t
&1;
l
=0, r
=n
/2;
while(l
<r
)
{
mid
=l
+r
>>1;
if(check(2*mid
+t
)==too_small
)l
=mid
+1;
else r
=mid
;
}
L
=l
;
l
=0, r
=n
/2;
while(l
<r
)
{
mid
=l
+r
+1>>1;
if(check(2*mid
+t
)==too_big
)r
=mid
-1;
else l
=mid
;
}
R
=l
;
if(check(2*L
+t
)==ok
)
{
for(i
=L
;i
<=R
;i
++)printf("%lld ",2*i
+t
);
}
else
{
printf("-1");
}
return 0;
}
