• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

CF818F Solution

开发技术 开发技术 2周前 (04-30) 6次浏览

题目链接

题解

易得,将割边全部放在一边,让剩下的点组完全图即可得出最多边数。二分答案((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("%lldn",ans);
	}
	return 0;
}

程序员灯塔
转载请注明原文链接:CF818F Solution
喜欢 (0)