题目描述 在霍格沃兹魔法学校，每年都要举行分院仪式。 分院帽今年不但负责将学生分到格兰芬多，赫奇帕奇，拉文克劳以及斯莱特林四个学院。还要把一部分学生分到新建起的一所学院 —— StandardDeviation学院。 也就是离入学标准还差一点的学院。（因为想来学习魔法的人真的太多了，大约有n人）但即使是这样，也不能招收太多人，准确来说，学校打算招收m人。 可是，这是一所公平的学校，如果一些同分的学生中，只有一些被招收走了，那么学校将会颜面尽失。老师十分不好办。 根据学校的记录，总共有k对人成绩相同，老师必须让录取公平、同时又和预期招收人数相差最少。 大家都去学习魔法了，老师就把任务交给你了。请你求出最优的录取人数。 输入 第一行三个整数n,m,k 接下来k行每行两个整数，a,b表示a,b两人的成绩相同 （n,m,k∈N*，1≤a,b≤n） 输出 一行，表示既不让同学们抗议，又与原来的m尽可能接近的选出学生的数目。(如果有两种方案与m的差的绝对值相等，选较小的一种：) 样例输入 Copy 4 3 2 2 1 3 4 样例输出 Copy 2 提示 解析: 这道题一开始认为最后的答案 不能超过预期人数m ，导致无限WA 先用并查集维护相同分数的个数，然后跑0/1背包。 物品数量:集合个数 物品价值:每个集合的元素个数 背包容量:n
最后我们还要判断与m差值最小的答案(这时答案很可能超过m)
#pragma GCC optimize(3,"Ofast","inline") #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e4+1000; int fa[N]; ll size[N]; ll a[N]; int n,m,k; ll dp[N]; int tot; int find(int x) { if(x!=fa[x]) return fa[x]=find(fa[x]); return fa[x]; } int main() { scanf("%d %d %d",&n,&m,&k); for(int i=0;i<=n;i++) fa[i]=i,size[i]=1; for(int i=1,u,v;i<=k;i++) { scanf("%d %d",&u,&v); int x=find(u); int y=find(v); if(x!=y) { fa[x]=y; size[y]+=size[x]; // size[x]=0; } } for(int i=1;i<=n;i++) if(find(i)==i) a[++tot]=size[find(i)]; dp[0]=0; for(int i=1;i<=tot;i++) for(int j=n;j>=a[i];j--) dp[j]=max(dp[j],dp[j-a[i]]+a[i]); ll ans=0x3f3f3f3f; ll pos; for(int i=0;i<=n;i++) { if(dp[i]!=0x3f3f3f3f) { if(abs(m-dp[i])<ans) ans=abs(m-dp[i]),pos=i; } } cout<<pos<<endl; }