ZOJ 3715 Kindergarten Election

本文主要是介绍ZOJ 3715 Kindergarten Election，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

n个人投票  唯一一个票数最多的人当选  1想当选  他可以通过给别人糖让不选他的人选他  问  最少需要多少糖

思路：

由于n比较小  可以枚举1当选时得了多少票  这样就可以贪心的使用糖

如果1当选时有i票  那么所有人都要先保证选票数<i  而且还要保证至少一个人<i-1  因为1还会投出一票

保证上述条件下  如果1票数已经超过i  则说明这次枚举是失败的  如果不到i  就尽量少用糖补到i

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define M 110int t,n,ans,tot;
int vot[M],get[M],vis[M];
struct node
{int cost,to,use;bool operator<(const node ff) const{return cost<ff.cost;}
}nd[M];int main()
{int i,j,k,tmp;scanf("%d",&t);while(t--){scanf("%d",&n);memset(get,0,sizeof(get));ans=2147483647;tot=0;for(i=2;i<=n;i++){scanf("%d",&vot[i]);get[vot[i]]++;}for(i=2;i<=n;i++){scanf("%d",&nd[tot].cost);if(vot[i]==1) continue;nd[tot].to=vot[i];nd[tot].use=0;tot++;}sort(nd,nd+tot);for(i=get[1];i<=n;i++){tmp=0;memcpy(vis,get,sizeof(int)*(n+1));for(j=0;j<tot;j++){if(vis[nd[j].to]>=i){nd[j].use=1;tmp+=nd[j].cost;vis[nd[j].to]--;vis[1]++;}}for(j=0;j<tot&&vis[1]<i;j++){if(!nd[j].use){nd[j].use=1;tmp+=nd[j].cost;vis[nd[j].to]--;vis[1]++;}}for(j=2;j<=n;j++){if(vis[j]<i-1) break;}if(j<=n&&vis[1]==i) ans=min(ans,tmp);for(j=0;j<tot;j++) nd[j].use=0;}printf("%d\n",ans);}return 0;
}

这篇关于ZOJ 3715 Kindergarten Election的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---