题解：P14478 手心

~~本题真的是黄吗？（蒟蒻不会，代码不长但细节多，对于才学最大独立集的OIER比较难想）。~~

思路

最大

我们先来看最大值怎么求。

因为

1\leq n \leq 10^9

，所以尝试构造解再求最大独立集的想法是不现实的。

所以，我们转而思考，最大独立集是一个集合，根据最大独立集的定义，最大独立集中的点两两不直接联通，我们可不可以枚举最大独立集的点数，让其他点连向它们？这样的话也符合最大独立集的定义。

可是，这样做有个问题，我们无法确定这个最大独立集是否是这种连边中最大的，除非其他点构成一个完全图。

我们可以转而想到枚举完全图的点的个数，其他点便成为了一个最大独立集。

所以，这种方法直接又好求，唯一的问题就是

1\leq n \leq 10^9

，直接枚举大小不现实，容易想到可以二分解决。

最小

最小值比较难想。

我们来看一个问题：

把一个 $n=12$ 的点集分成两个完全图，转化成 $11,1$ 好还是转化成 $6,6$ 好（每个数字是每个完全图的大小）？

显然是后者，每个完全图只能贡献一个点，而后者显然是在满足条件下所需边数最小的方案。

为什么不用求最大值的方法？因为求最大值只是枚举一个完全图，其他点都是最大独立集中的一个，肯定没有分成几个完全图贡献的少。

这里也是用二分枚举分成几个完全图，对于一组一组分后剩下的那些点（也就是

n\bmod mid,mid

是分成的完全图个数），直接平均分到所有完全图中即可。

代码

CPP

#include<bits/stdc++.h>
#define int long long
typedef long long ll;
using namespace std;
const int N=2e5+114;
int T,n,m;
signed main()
{
    cin>>T;
    while(T--)
    {
        cin>>n>>m;
        if(m==0)
        {
            cout<<n<<" "<<n<<endl;
            continue;
        }
        int l=1,r=n;
        int mid=0,ans=0;
        while(l<=r)
        {
            mid=l+r>>1;
            if(mid*(mid-1)/2+(n-mid)*(mid-1)>=m)ans=mid,r=mid-1;
            else l=mid+1;
        }
        cout<<n-ans+1<<" ";//最大
        ans=0,l=1,r=n;
        while(l<=r)
        {
            mid=l+r>>1;
            if((n/mid)*(n/mid-1)*(mid-n%mid)/2+(1+n/mid)*(n/mid)/2*(n%mid)<=m)ans=mid,r=mid-1;
            else l=mid+1;
        }
        cout<<ans<<endl;//最小
    }
    return 0;
}

文章操作

思路

最大

最小

代码

相关推荐

评论

题解：P14478 手心