二分+求和公式（这个题的精度错了无数次）

以五个顶点的完全图为例

删去四个边(共删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

所以通过上式，可以推导出公式为 $(n-1)*i-i*(i-1)/2$ ，化简一下： $(n-1-mid+n)*mid/2$

#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;
}

完全图

全站热榜