作者: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;
}