C.完全图 (二分)

绝地灬酷狼 2023-05-28 09:51 47阅读 0赞

[C.完全图][C.]

题意：  
给你一个n个顶点的完全图，让你删除不超过m条边，问你最多可以分成多少个连通分量。

题解：  
n个顶点的完全图，两两都有一点边，求最多的连通分量，我们贪心肯定每次分离出1个顶点的连图分量。  
计算出每次分离1个顶点需要的边分别为n-1,n-2,n-3,n-4…这些总和不超过m  
即对于分离k个顶点：(k \* (n-1+n-k)) / 2 <=m 然后二分查找

坑点1.我容易右区间为n，这是错的，应该是右区间n-1，分离了最多n-1个，最后在答案+1就可。  
坑点2. 使用\_\_int128，数据范围很大。

code:

#include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<map>
    #include<queue>
    #include<vector>
    #include<set>
    #include<sstream>
    using namespace std;
    typedef unsigned long long ll;
    const ll maxn=1e6+10;
    const ll inf=0x3f3f3f3f3f3f3f3f;
    void io(){ ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
    ll n,m;
    __int128 solve(__int128 x)
    { 
    	return (n-1+n-x)*x/2<=m;
    } 
    int main()
    { 
    	io();
    	ll t;
    	cin>>t;
    	while(t--)
    	{ 
    		cin>>n>>m;
    		__int128 l=0,r=n-1,k=0;
    		while(l<=r)
    		{ 
    			__int128 mid=(l+r)>>1;
    			if(solve(mid))
    			{ 	
    				l=mid+1;
    				k=mid;
    			}
    			else
    				r=mid-1;
    		}
    		cout<<(ll)k+1<<endl;
    	}
    	return 0;
    }

[C.]: https://ac.nowcoder.com/acm/contest/4784/C

发表评论取消回复

表情：

评论列表（有 0 条评论，47人围观）

还没有评论，来说两句吧...

相关阅读

相关 C.完全图 (二分)

[C.完全图][C.] 题意：给你一个n个顶点的完全图，让你删除不超过m条边，问你最多可以分成多少个连通分量。题解： n个顶点的完全图，两两都有一点边，求最多的

绝地灬酷狼/ 2023年05月28日 09:51/ 0 赞/ 48 阅读

相关 C++字符串完全指引之二 —— 字符串封装类

C++字符串完全指引之二 —— 字符串封装类原著：Michael Dunn 作者：Chengjie Sun 原文出处：CodeProject：Th

谁借莪１个温暖的怀抱￠/ 2022年09月19日 12:20/ 0 赞/ 274 阅读

相关 C++字符串完全指南 - Win32字符编码（二）

Win32 API中的MBCS 和 Unicode API的二个字符集也许你没有注意到，Win32的API和消息中的字符串处理函数有二种，一种为MCBS字符串，另

￡神魔★判官ぃ/ 2022年09月17日 06:19/ 0 赞/ 273 阅读

相关 C++打印完全二叉树

思路：完全二叉树可以采用数组顺序存储，而且除最后一层外其余各层都是满的。则可以采用逆序打印的方式，先确定最底层的节点位置及数目，进而确定其上各层的节点位置。打印效果

叁歲伎倆/ 2022年09月11日 10:16/ 0 赞/ 94 阅读

相关 C++字符串完全指引之二

[点击打开链接][Link 1] <table> <tbody> <tr> <td> <p><strong>引言</strong></p>

末蓝、/ 2022年08月06日 01:27/ 0 赞/ 264 阅读

相关 Courses（二分图完全匹配）

Courses Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65536/32768 K (Java

向右看齐/ 2022年08月01日 06:05/ 0 赞/ 236 阅读

相关 7-2 是否完全二叉搜索树（30 分）

将一系列给定数字顺序插入一个初始为空的二叉搜索树（定义为左子树键值大，右子树键值小），你需要判断最后的树是否一棵完全二叉树，并且给出其层序遍历的结果。输入格式：输入

缺乏、安全感/ 2022年04月14日 02:24/ 0 赞/ 247 阅读

相关 7-15 完全二叉搜索树（30 分）

题目描述：一个无重复的非负整数序列，必定对应唯一的一棵形状为完全二叉树的二叉搜索树。本题就要求你输出这棵树的层序遍历序列。输入格式：首先第一行给出一个正整数

水深无声/ 2022年03月10日 07:16/ 0 赞/ 273 阅读

相关 L3-010 是否完全二叉搜索树（30 分)

L3-010 是否完全二叉搜索树（30 分) 将一系列给定数字顺序插入一个初始为空的二叉搜索树（定义为左子树键值大，右子树键值小），你需要判断最后的树是否一棵完全二叉树，并

系统管理员/ 2022年02月27日 05:24/ 0 赞/ 283 阅读

相关 CF544C：Writing Code（二维完全背包）

C. Writing Code time limit per test 3 seconds memory limit per test 256 megabytes i

刺骨的言语ヽ痛彻心扉/ 2022年01月05日 13:11/ 0 赞/ 215 阅读