完全图-牛客小白月赛23

题目描述
在图论的数学领域，完全图是一个简单的无向图，其中每对不同的顶点之间都恰连有一条边相连。————百度百科
现在给定一个包含 {n}n 个顶点的完全图，你可以删掉图中的一些边，但是删掉的边不能超过 {m}m 条，请问删去边之后的图最多能有几个连通分量？
输入描述:
第一行包含一个数字 {T}T，表示测试数据组数
接下来 {T}T 行，每行两个正整数{n}n,{m}m，中间用空格隔开
输出描述:
输出 {T}T 行，每行一个整数表示答案
示例1
输入
复制
2
5 1
5 5
输出
复制
1
2
备注:
1\le T\le 10000 , 1 \le n,m \le 10^{18}1≤T≤10000,1≤n,m≤10^18
题解：贪心的思想，拆出第一个分量我们需要拿走n-1条边，第二个需要拿走n-1条边，因此，我们拆出x个分量需要拿出nx-x(x+1)/2条边，这个数量必须小于等于m。因此二分计算这个x。题目一个难点在于数据范围是ll的，当你使用乘法nx时会越界。此题目并不需要准确计算值，只需要比较结果和m的大小。所以用double类型来计算和比较。

#include <bits/stdc++.h>//ASI
typedef long long ll;
using namespace std;
ll n,t,m;
int check(ll x)
{
    return 1.0*n*x-(x+1.0)*x/2-m<=0.000001;
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    int i,j;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        if(m+0.000001>=1.0*n*(1.0*n-1)/2)
        {
            cout<<n<<endl;
            continue;
        }
        ll l=0,r=n,mid,best=0;
        while(l<=r)
        {
            mid=(l+r)/2;
            if(check(mid))
            {
                best=mid;
                l=mid+1;
            }
            else
                r=mid-1;
        }
        cout<<best+1<<endl;
    }
    return 0;
}