欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

牛客 - 完全图(二分)

程序员文章站 2024-03-17 15:05:22
...

题目链接:点击查看

题目大意:给出一个完全图,现在要求删掉不超过 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;
}

 

相关标签: 二分