K

K

K - Kindergarten Election

  ZOJ - 3715  从max(1, num[1])开始枚举，一直到n-1，每一个枚举的数的意思是：这个票数可以让1号当选唯一的leader,所以在每此枚举时，要从2号到n号，遍历一遍，如果num[i] >= num[1]则就要在支持i号的人当中选出最小代价的num[i] - num[1] + 1位，用糖果收买他，并使nownum ++(每此枚举的初始值是num[1])，注意记录代价，一个遍历完以后，如果nownum==当前枚举的数时，就把这次枚举的总代价和Min相比，取较小的值，，如果nownum > num[1].那么这种情况是不合法的，不符合我们前面枚举的意图，如果nownum < num[1],那么就从剩下的没有被收买的人当中，在收买num[1] - nownum 个人，记录下代价和Min比较，取较小值，思路就是这样

#include <bits/stdc++.h>using namespace std;const int inf = 0X3f3f3f3f;
int vote[110],num[110];
int val[110];
bool vis[110];
bool tmp(int x, int y)
{return val[x] < val[y];
}
int main()
{int sum;scanf("%d", &sum);while(sum --){int n;memset(num, 0, sizeof(num));scanf("%d", &n);for(int i = 2; i <= n; i ++){scanf("%d", &vote[i]);num[vote[i]] ++;}for(int i = 2; i <= n; i ++){scanf("%d", &val[i]);}int Min = inf;int cost;int nownum;for(int i = max(1, num[1]); i < n; i ++){memset(vis, false, sizeof(vis));cost = 0;nownum = num[1];for(int j = 2; j <= n; j ++){if(num[j] >= i){int shu[110];int cnt = 0;int len = num[j] - i + 1;for(int z = 2; z <= n; z ++){if(vote[z] == j){shu[cnt ++] = z;}}sort(shu, shu + cnt, tmp);for(int z = 0; z < len; z ++){//cout << shu[z] << endl;cost += val[shu[z]];vis[shu[z]] = true;nownum ++;}}}if(nownum > i) continue;int len = i - nownum;//cout << len << endl;int shu[110];int cnt = 0;for(int j = 2; j <= n; j ++){if(!vis[j] && vote[j] != 1){shu[cnt ++] = j;}}sort(shu, shu + cnt, tmp);for(int j = 0; j < len; j ++){cost += val[shu[j]];// cout << shu[j] << endl;}Min = min(cost, Min);}cout << Min <<endl;}return 0;
}