[ CodeForces 1065 B ] Vasya and Isolated Vertices

(\)

(Description)

求一个(N)个点(M)条边的无向图，点度为 (0) 的点最多和最少的数量。

(Nle 10^5,Mle frac {N imes (N-1)}{2})

(\)

(Solution)

关于最少的数量，注意到一条边会增加两个点度，所以最多能带来 (2M) 个点度，最少的零点度点数就是 (max(N-2M,0))。

关于最多的数量，要知道 (N) 个点的完全图边数是 (frac {N imes (N-1)}{2}) 。然后就可以二分上界是什么了。

事实上线性扫一下并不会 (T) ......

(\)

(Code)

#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-ans);
  return 0;
}