有n个小朋友竞选班长，一号想当班长，每个人都必须选择一个人当班长，并且不可以选择自己，并且每个人都有一个权值ai，这个权值就是如果1想让这个人改变主意选择自己当班长就得给他ai个糖果，只有当1的票数是唯一最多的时候，1才能竞选班长，问1竞选班长的最小花费糖果数。
思路
昨天练习赛的最后一个题，今天才AC，这个题目我们可以用贪心的方法，记得当时自己看完也马上感觉是贪心，可以因为选择了错误的贪心方法和策略，导致写了很长，而且越写越蒙，最后写的脑袋短路了，悲剧啊，说下正解，我们可以枚举1号竞选时的票数,对于每一次枚举，如果当前有人的票数比1号的x多，那么就把他减少到x-1（肯定是挑选费用最小的）,然后把当前的票数加到1身上，最后如果1号的票数大于当前的枚举票数，枚举失败，如果等于，那么就更新最优值，如果小于，就在剩下的没有选则1的里面挑选几个最小的补上去，这样就行了，说到这，可能有人去会想，1不是也要投一票吗，怎么没考虑，其实根本不用管1这票投给了谁，因为只有出现这样的状态这一票才会有影响x x-1 x-1 x-1 x-1.....但是这个状态是不存在的，想一下，这个题目每个人最多投一票，如果1的票数为x，那么那个状态的总票数就是 x + (x - 1) * (n - 1) + 1,其实x是大于等于2的(这个地方自己想，很好想)，那么就会得到 2 + （2 - 1） * （n - 1）+ 1 = n + 2,而每个人都一票，总票数是n，所以矛盾，所以不存在那种状态，所以不用考虑1的那票投给了谁。
#include<stdio.h>
#include<algorithm>
#include<string.h>
#define N 120
using namespace std;
typedef struct
{
int to ,next;
}STAR;
typedef struct
{
int id ,cost;
}NODE;
STAR E[N];
NODE node[N];
int list[N] ,tot;
int now[N] ,mark[N] ,MARK[N];
int cost[N];
void add(int a ,int b)
{
E[++tot].to = b;
E[tot].next = list[a];
list[a] = tot;
}
bool camp(NODE a ,NODE b)
{
return a.cost < b.cost;
}
int main ()
{
int t ,n ,i ,j ,a;
scanf("%d" ,&t);
while(t--)
{
scanf("%d" ,&n);
memset(list ,0 ,sizeof(list)) ,tot = 1;
memset(mark ,0 ,sizeof(mark));
memset(MARK ,0 ,sizeof(MARK));
memset(now ,0 ,sizeof(now));
for(i = 2 ;i <= n ;i ++)
{
scanf("%d" ,&a);
now[a] ++;
if(a == 1) MARK[i] = 1;
add(a ,i);
}
for(i = 2 ;i <= n ;i ++)
scanf("%d" ,&cost[i]);
int star = 1;
if(star < now[1]) star = now[1];
int min = 1000000000;
for(i = star ;i <= n ;i ++)
{
for(j = 1 ;j <= n ;j ++)
mark[j] = MARK[j];
int sum = 0 ,ss = 0;
for(j = 2 ;j <= n ;j ++)
{
if(now[j] < i) continue;
int id = 0;
for(int k = list[j] ;k ;k = E[k].next)
{
int to = E[k].to;
if(mark[to]) continue;
node[++id].cost = cost[to];
node[id].id = to;
}
sort(node + 1 ,node + id + 1 ,camp);
for(int k = 1 ;k <= now[j] - i + 1 ;k ++)
{
sum += node[k].cost ;
ss ++ ;
mark[node[k].id] = 1;
}
}
if(ss + now[1] == i)
{
if(min > sum) min = sum;
}
else if(ss + now[1] > i)
continue;
int id = 0;
int tmp[N];
for(j = 2 ;j <= n ;j ++)
for(int k = list[j] ;k ;k = E[k].next)
if(!mark[E[k].to])tmp[++id] = cost[E[k].to];
sort(tmp + 1 ,tmp + id + 1);
for(j = 1 ;j <= i - (ss + now[1]) ;j ++)
sum += tmp[j];
if(min > sum) min = sum;
}
printf("%d
" ,min);
}
return 0;
}