首页 > 代码库 > CODEVS3372 选学霸 (easy)
CODEVS3372 选学霸 (easy)
老师想从N名学生中选M人当学霸,但有K对人实力相当,如果实力相当的人中,一部分被选上,另一部分没有,同学们就会抗议。所以老师想请你帮他求出他该选多少学霸,才能既不让同学们抗议,又与原来的M尽可能接近。
思路:将实力相当的人都并到一个集合中,统计出集合中元素的个数。然后做一个类似01背包(布尔型)的东西,找到最优解就可以了。
code:
#include<cstdio>
#include<iostream>
using namespace std;
int sum[30001]={0},fa[30001]={0},v[30001]={0};
bool visit[30001]={0},f[30001]={false};
int rool(int x)
{
if (fa[x]!=x) fa[x]=rool(fa[x]);
return fa[x];
}
int main()
{
int n,m,k,i,j,a,b,r1,r2,nn=0,maxn,minn;
cin>>n>>m>>k;
for (i=1;i<=n;++i)
{
fa[i]=i;
sum[i]=1;
}
for (i=1;i<=k;++i)
{
cin>>a>>b;
r1=rool(a);
r2=rool(b);
if (r1!=r2)
{
fa[r1]=r2;
sum[r2]=sum[r2]+sum[r1];
}
}
for (i=1;i<=n;++i)
{
r1=rool(i);
if (!visit[r1])
{
++nn;
v[nn]=sum[r1];
visit[r1]=true;
}
}
f[0]=true;
for (i=1;i<=nn;++i)
for (j=n;j>=v[i];--j)
f[j]=f[j]||f[j-v[i]];
maxn=0;
minn=n;
for (i=m;i>=1;--i)
if (f[i])
{
maxn=i;
break;
}
for (i=m+1;i<=n;++i)
if (f[i])
{
minn=i;
break;
}
if (m-maxn<minn-m) cout<<maxn<<endl;
if (m-maxn>minn-m) cout<<minn<<endl;
if (m-maxn==minn-m) cout<<maxn<<endl;
}
(code好长啊,被组里的鄙视了。。。吴鼐)
CODEVS3372 选学霸 (easy)