完全图(二分+求和)

作者：mywgo
链接：https://ac.nowcoder.com/discuss/388973?type=101&order=0&pos=1&page=0
来源：牛客网

二分+求和公式（这个题的精度错了无数次）
以五个顶点的完全图为例
删去四个边(共删4个)，形成两个连通图-->再删去三个边（共删4+3），形成三个完全图-->再删去两个边（共删4+3+2），形成四个完全图-->再删去一个边（共删4+3+2+1），形成五个完全图。
因此，只要判断区间就可以。
五个顶点的完全图共有5个区间。（使用两分法查找）
每个区间对应的范围可以推导出来：
0：0
1：0+4
2：0+4+（4-1）
3：0+4+（4-1）+（4-2）
4：0+4+（4-1）+（4-2）+（4-1）-->(5-1)4-4(3)/2

所以通过上式，可以推导出公式为 ，化简一下：

作者：mywgo
链接：https://ac.nowcoder.com/discuss/388973?type=101&order=0&pos=1&page=0
来源：牛客网

#include<iostream>
#include<vector>
#include<string>
#include<algorithm> 
#include<map>
#include<climits> 
using namespace std;
typedef long long ll; 
long double n,m; 
long double check(ll mid){//求和公式 
    return (n-1-mid+n)*mid/2.0;
}
int main(){
    ll t;
    cin>>t;
    while(t--){
        cin>>n>>m;
        ll left=0,right=n-1;
        while(left<=right){
            ll mid=(left+right)/2;
            if(check(mid)>m){
                right=mid-1;
            }else{
                left=mid+1;
            }
        }
        cout<<left<<endl;  
    }
    return 0;
}