cf Educational Codeforces Round 52 B. Vasya and Isolated Vertices

原题：
B. Vasya and Isolated Vertices
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
Vasya has got an undirected graph consisting of n vertices and m edges. This graph doesn’t contain any self-loops or multiple edges. Self-loop is an edge connecting a vertex to itself. Multiple edges are a pair of edges such that they connect the same pair of vertices. Since the graph is undirected, the pair of edges (1,2) and (2,1) is considered to be multiple edges. Isolated vertex of the graph is a vertex such that there is no edge connecting this vertex to any other vertex.

Vasya wants to know the minimum and maximum possible number of isolated vertices in an undirected graph consisting of
n vertices and m edges.

Input
The only line contains two integers n and m (1≤n≤10^5,0≤m≤n(n−1)/2).

It is guaranteed that there exists a graph without any self-loops or multiple edges with such number of vertices and edges.

Output
In the only line print two numbers min and max — the minimum and maximum number of isolated vertices, respectively.

Examples
input
4 2
output
0 1
input
3 1
output
1 1

Note
In the first example it is possible to construct a graph with 0 isolated vertices: for example, it should contain edges
(1,2) and (3,4). To get one isolated vertex, we may construct a graph with edges (1,2) and (1,3).
In the second example the graph will always contain exactly one isolated vertex.

中文：
给你两个数n和m，问你构造成无向图，这个无向图最少和最多能有多少个没有任何边连接的顶点。（没有边指向自身，没有重边）

代码：

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
ll n,m;
int main()
{
    ios::sync_with_stdio(false);
    while(cin>>n>>m)
    {
        if(m==0)
        {
            cout<<n<<" "<<n<<endl;
            continue;
        }
        ll ans1,ans2;


        ans1=n-2*m;

        ll tmp;

        tmp=0;
        ans2=0;
        for(ll i=2;i<=n;i++)
        {
            tmp=(i*(i-1))/2;
            if(tmp>=m)
            {
                ans2=n-i;
                break;
            }
        }

        if(ans1<0)
            ans1=0;
        if(ans2<0)
            ans2=0;
        cout<<ans1<<" "<<ans2<<endl;


    }
    return 0;
}

思路：

n个定点构造一个有m条边的无向图，要求孤立顶点（没有任何边相连的顶点）最少，由于一条边可以连接两个定点，所以尽量让每一条边都连接两个没有任何边的顶点，可以知道答案就是定点数除以2.

要求孤立顶点最多，那么尽量把边连刀已经有边相连的顶点上，无向图x个边最多可以连接x(x-1)/2个节点，（题里都给你公式了-_-），把m条边使用完，判断最后剩下多少顶点就是最多顶点数。