Description 求一个N个点M条边的无向图，点度为 0 的点最多和最少的数量。
N≤105,M≤N×(N−1)2
Solution 关于最少的数量，注意到一条边会增加两个点度，所以最多能带来 2M 个点度，最少的零点度点数就是 max(N−2M,0)。
关于最多的数量，要知道 N 个点的完全图边数是 N×(N−1)2 。然后就可以二分上界是什么了。
可以打表递推，也可以直接利用完全图的性质，甚至有公式
c++代码一：利用行政扫一遍
#include<cmath> #include<cstdio> #include<cctype> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define N 100010 #define R register #define gc getchar using namespace std; typedef long long ll; inline int rd(){ int x=0; bool f=0; char c=gc(); while(!isdigit(c)){if(c=='-')f=1;c=gc();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();} return f?-x:x; } ll n,m,ans,cnt[N]; int main(){ scanf("%lld%lld",&n,&m); printf("%lld ",max(0ll,n-m*2)); while(m>ans*(ans-1)/2) ++ans; printf("%lld\n",n-ans); return 0; }最小值 显然，每次连一条边，可以使得两个点不再是孤立点。
所以答案为max{n -2m , 0} 最大值 连的边一定要尽量重复。考虑构造局部的完全图。
先构造一个点的完全图， 再到两个，再到三个，直到再加会超出。
但是要特判吗m= 1和m=0。
具体实现看代码。
#include <bits/stdc++.h> #define re register typedef int mainint; #define int long long using namespace std; inline int read() { int X=0,w=1; char c=getchar(); while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); } while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar(); return X*w; } namespace SubTask1 { //求最小 inline void work(int n,int m) { if (n>m*2) printf("%d ",n-m*2); else printf("0 "); } } namespace SubTask2 { //求最大 inline void work(int n,int m) { if (m==0) printf("%d\n",n); else if (m==1) printf("%d\n",n-2); else { int now=2,sum=0; while (sum+now-1<m) sum+=(now-1),now++; printf("%d\n",n-now); } } } mainint main() { int n=read(),m=read(); SubTask1::work(n,m); SubTask2::work(n,m); return 0; }C++代码三 ： 公式
题解：
最大孤立点：运用完全图m=n*(n-1)/2得到公式----maxi = n-(1+sqrt(1+8*m))/2;
最小孤立点：mini = n-2*m; （注意：当mini < 0时，需要让mini=0）
#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cmath> #include <cstring> #include <vector> #include <set> #include <sstream> #include <stack> using namespace std; int main() { long long n,m; while(cin>>n>>m){ long long maxi = 0,mini = 0; maxi = n-(1+sqrt(1+8*m))/2; mini = n-2*m; if(mini < 0) mini = 0; if(m == 0){ maxi = n; mini = n; } cout<<mini<<" "<<maxi<<endl; } return 0; }