C/C++教程

CF818F Solution

本文主要是介绍CF818F Solution,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目链接

题解

易得,将割边全部放在一边,让剩下的点组完全图即可得出最多边数。二分答案(\(m\)),如果\(\lceil \frac{m}{2} \rceil+\)完全图边数\(\ge m\)即可行。

AC代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,tmp;
bool check(int m)
{
	tmp=n-(m+1)/2;//完全图中点的个数
	if(tmp<=0) return 0;
	return tmp*(tmp-1)/2+(m+1)/2>=m;
}
signed main()
{
	scanf("%lld",&q);
	while(q--)
	{
		scanf("%lld",&n);
		int l=0,r=1e18,ans=0;
		while(l<=r)
		{
			int mid=(l+r)/2;
			if(check(mid)) {l=mid+1; ans=mid;}
			else r=mid-1;
		}
		printf("%lld\n",ans);
	}
	return 0;
}
这篇关于CF818F Solution的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!