牛客 - 完全图(二分)

题目链接：点击查看

题目大意：给出一个完全图，现在要求删掉不超过 m 条边，使得连通块的个数尽量多，输出最多连通块的个数

题目分析：比赛的时候正着想的，也就是直接求需要删掉多少条辨，找出来的规律也不知道对不对，反正是因为爆longlong了止步不前，一开始注意到了二分会爆longlong，于是换成倍增，比赛结束后意识到倍增也是会爆longlong的

其实这个题反着想是比较容易的，题解说的很清楚了，直接放题解吧：

 然后为了解决爆longlong的问题，在运算的过程中可以强制转换为__int128就好了，算是学到了一波吧

代码：
 

#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
using namespace std;
      
typedef long long LL;

typedef unsigned long long ull;
      
const int inf=0x3f3f3f3f;
 
const int N=1e5+100;

int main()
{
#ifndef ONLINE_JUDGE
//	freopen("input.txt","r",stdin);
//	freopen("output.txt","w",stdout);
#endif
//	ios::sync_with_stdio(false);
    int w;
    cin>>w;
    while(w--)
	{
		LL n,m;
		scanf("%lld%lld",&n,&m);
		__int128 mark=max((__int128)0,(__int128)n*(n-1)/2-m);
		LL l=0,r=n,ans;
		while(l<=r)
		{
			LL mid=l+r>>1;
			if((__int128)mid*(mid+1)/2>=mark)
			{
				ans=mid;
				r=mid-1;
			}
			else
				l=mid+1;
		}
		printf("%lld\n",n-ans);
	}
    
    
    
    
    
    
    
    
    
    
    
    
    return 0;
}