二分+求和公式（这个题的精度错了无数次）
以五个顶点的完全图为例
删去四个边(共删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
所以通过上式，可以推导出公式为*i-i*(i-1)%2F2)
，化简一下：*mid%2F2)
#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;
} 
全部评论
(1) 回帖