http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3715
题意：有N个孩子投票选举leader，不能自己选自己。Sheldon想做leader，所以他就用糖果贿赂其他人，别的孩子就会将票投给他。问Sheldon最少要送多少糖果。
思路：枚举Sheldon做leader的票数（Sheldon原始的票数<= i < 100），将所有票数比他高的kid的得票一直减到票数比他少(按照给得票高的人投票的孩子所要的糖果数从小到大减)，如果最后Sheldon的票数还是不够，就贿赂没投给他票且要的糖果数少的孩纸。最后输出花费的最少的糖果数。
1 #include <stdio.h> 2 #include <string.h> 3 #include <algorithm> 4 using namespace std; 5 const int INF=1<<28; 6 int m[102][102]; 7 int vis[102],sum[102]; 8 9 struct node 10 { 11 int kid; 12 int candy; 13 friend bool operator <(node a,node b) 14 { 15 return a.candy < b.candy; //按糖果数排序 16 } 17 } c[102]; 18 int main() 19 { 20 int t,n,x; 21 scanf("%d",&t); 22 while(t--) 23 { 24 scanf("%d",&n); 25 memset(sum,0,sizeof(sum)); 26 memset(m,0,sizeof(m)); 27 for (int i = 2; i <= n; i++) 28 { 29 scanf("%d",&x); 30 m[i][x] = 1;//表示第i个孩子将票投给了x 31 sum[x]++;//记录每个人的得票数 32 } 33 for (int i = 2; i <= n; i++) 34 { 35 scanf("%d",&x); 36 c[i-2].kid = i; //将贿赂第i个孩子所需的糖果数保存在数组c中 37 c[i-2].candy = x; 38 } 39 sort(c,c+n-1);//按糖果数排序 40 int Min = INF; 41 for (int i = sum[1]; i < n; i++)//枚举胜出的票数 42 { 43 if(i==0) continue; 44 int get = sum[1];//Sheldon的原始票数 45 int num = 0; //记录所需的糖果数 46 memset(vis,0,sizeof(vis)); 47 for (int j = 2; j <= n; j++) 48 { 49 int temp = sum[j]; 50 if (temp >= i)//处理所有票数比他高的 51 { 52 for (int k = 0; k < n-1; k++) 53 { 54 if (m[c[k].kid][j]) 55 { 56 vis[c[k].kid] = 1; 57 num+=c[k].candy; 58 get++; 59 temp--; 60 if (temp < i) 61 break; 62 } 63 } 64 } 65 } 66 if (get <= i) 67 { 68 for (int k = 0; k < n-1; k++) 69 { 70 if (get==i) 71 break; 72 if (!vis[c[k].kid]) 73 { 74 get++; 75 num+=c[k].candy; 76 } 77 } 78 if(num < Min) Min = num; 79 } 80 } 81 printf("%d\n",Min); 82 } 83 return 0; 84 }
