链接
https://ac.nowcoder.com/acm/contest/4784/C
题意
给定一个包含 $n$ 个顶点的完全图，可以删掉图中的一些边，但是删掉的边不能超过 $m$ 条，问删去边之后的图最多能有几个连通分量
思路
反过来想，要添加$C_n^2−m$条边，让连通块尽量多
形成 $n-1,n-2,n-3,…,n-i$ 个连通块能用完的最大边数依次为：$1,3,6,…,\frac{i(i+1)}{2}$
二分即可
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| #include<bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int T;cin>>T;
while(T--) {
long long n,m;
cin>>n>>m;
__int128 x=(__int128)n*(n-1)/2-m;
long long l=0,r=n,ans;
while(l<r) {
long long mid=l+r+1>>1;
if(x<=(__int128)(n-mid)*(n-mid+1)/2) l=mid;
else r=mid-1;
}
cout<<l<<endl;
}
return 0;
}
|