题目链接:http://codeforces.com/contest/1065/problem/B
题目大意:给你n个点,m条边,让你连接成一个无向图,剩余孤立点的点的最大数量和最小数量是多少?

思路:当时翻译的锅:此图不包含任何自循环,我们翻译成是不能有环,wa了2次。
最小的孤立点数:max(0, n-2*m)两个点连一条边
最大的孤立点数:用最少的点连成一个完全图,如果还 边剩余再加一个点入完全图。

因为n个点形成完全图要(n)*(n-1)/2条边;
所以要解方程,因为m可能不是整数解,
这里我用了set存了n=1…1e5的解直接lower_bound(),队友用了解方程对解向上取整。

思考:这题还是方程的解代码写的比较简单。感觉自己特别喜欢用set优化,哈哈哈哈

set的代码

#include<bits/stdc++.h>
using namespace std;

int a[200005];
int s[200005];

struct fz
{
    long long i;
    long long s;
};

struct cu
{
    int operator()(fz a, fz b)
    {
        return a.s<b.s;
    }
};

set<fz,cu> st;
int main()
{
    for(long long i=1;i<=1e5;i++)
    {
        fz p;
        p.i=i;
        p.s=(i)*(i-1)/2;
        st.insert(p);
    }
    long long n, m;
    scanf("%lld%lld",&n,&m);
    if(m==0)
        cout<<n<<' '<<n<<endl;
    else
    {
        fz p;
        p.s=m;
        long long a=0;
        a=max(a, n-2*m);
        fz b=*st.lower_bound(p);

        cout<<a<<" "<<n-b.i<<endl;

    }

    return 0;
}

方程的解

#include<bits/stdc++.h>
using namespace std;

int a[200005];
int s[200005];

int main()
{
    long long n, m;
    scanf("%lld%lld",&n,&m);
    if(m==0)
        cout<<n<<' '<<n<<endl;
    else
    {
        long long a=0;
        a=max(a, n-2*m);
        double b=ceil((1+sqrt(1+8.0*m))/2);

        cout<<a<<" "<<n-b<<endl;

    }

    return 0;
}