P2170 选学霸

P2170 选学霸

题目描述 老师想从N名学生中选M人当学霸，但有K对人实力相当，如果实力相当的人中，一部分被选上，另一部分没有，同学们就会抗议。所以老师想请你帮他求出他该选多少学霸，才能既不让同学们抗议，又与原来的M尽可能接近 (如果有两种方案与M的差的绝对值相等，选较小的一种:)

---

调试日志： 背包内层循环变量写成了k

---

Solution

选能力相同的你就得把能力为这个的全部选上， 求最终选多少人和原定选择人数尽可能接近 先并查集一下， 每个块维护一个大小 现在一整块一整块的选就好了 可行性背包搞一下即可 最后从中间开始往两边枚举可行的就得

Code

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<climits>
#define LL long long
#define REP(i, x, y) for(int i = (x);i <= (y);i++)
using namespace std;
int RD(){
    int out = 0,flag = 1;char c = getchar();
    while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}
    while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}
    return flag * out;
    }
const int maxn = 80019;
int num, nr, k;
int father[maxn], size[maxn];
int findfather(int v){
	if(father[v] == v)return v;
	return father[v] = findfather(father[v]);
	}
void Union(int a, int b){
	int faA = findfather(a), faB = findfather(b);
	if(faA != faB){
		size[faB] += size[faA];
		father[faA] = faB;
		}
	}
int w[maxn], cnt;
int dp[maxn];
int main(){
	num = RD(), k = RD(), nr = RD();
	REP(i, 1, num)father[i] = i, size[i] = 1;
	REP(i, 1, nr){
		int x = RD(), y = RD();
		Union(x, y);
		}
	dp[0] = 1;
	REP(i, 1, num)if(father[i] == i)w[++cnt] = size[i];
	REP(i, 1, cnt){
		for(int j = k * 2;j >= w[i];j--){
			dp[j] |= dp[j - w[i]];
			}
		}
	REP(i, 0, k){
		if(dp[k - i]){printf("%d
", k - i);return 0;}
		else if(dp[k + i]){printf("%d
", k + i);return 0;}
		}
	}