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