[ CodeForces 1065 B ] Vasya and Isolated Vertices

\(\\\)

\(Description\)

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

\(N\le 10^5,M\le \frac {N\times (N-1)}{2}\)

\(\\\)

\(Solution\)

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

关于最多的数量，要知道 \(N\) 个点的完全图边数是 \(\frac {N\times (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",n-ans);

  return 0;

}

巴特西

[ CodeForces 1065 B ] Vasya and Isolated Vertices

\(Description\)

\(Solution\)

\(Code\)

最新文章

热门文章