牛客小白月赛23C——完全图

网址：https://ac.nowcoder.com/acm/contest/4784/C

题目描述

在图论的数学领域，完全图是一个简单的无向图，其中每对不同的顶点之间都恰连有一条边相连。————百度百科
现在给定一个包含 {n}n 个顶点的完全图，你可以删掉图中的一些边，但是删掉的边不能超过 {m}m 条，请问删去边之后的图最多能有几个连通分量？

输入描述:

第一行包含一个数字 {T}T，表示测试数据组数
接下来 {T}T 行，每行两个正整数{n}n,{m}m，中间用空格隔开

输出描述:

输出 {T}T 行，每行一个整数表示答案

输入

2
5 1
5 5

输出

1
2

备注:

1≤T≤10000,1≤n,m≤10^18

题解：

这里要明白对于一个结点为n的完全图，如果要分为两份，一份x,一份y,那么所需要断开的边数为xy,因为这两份不能相连，而原本其中一份(有x个结点)中的所有结点(共x个)，每个都与另一份中的所有结点(共y个结点)都相连，多以最少需要断去xy条边，而x+y=n（常数），所以其中一份为1时最好。
那么每次加一个连通分量，所需要最少短边:n-1，n-2,....n-k;

AC代码：

#include<iostream>
#include<cmath>
using namespace std;
const long long int maxn=1e18+10;
long long int n,m,ans,mid;
bool Check(long long int x){
    if(x*(2*n-x-1)/2>m) return true;
    else return false;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        cin>>n>>m;        
        long long int l=0,r=min(maxn*2/n,n);
        ans=r;
        while(l<=r){
            mid=(l+r)/2;
            if(Check(mid)) ans=mid,r=mid-1;
            else l=mid+1;
        }
        cout<<ans<<endl;
    }
    return 0;
} 

打卡第12天，原明日更好。