Skip to content

Instantly share code, notes, and snippets.

@VOID001 VOID001/K.cpp
Created Dec 18, 2014

Embed
What would you like to do?
/*************************************************************************
> File Name: K.cpp
> Author: VOID_133
> ###################
> Mail: ###################
> Created Time: 2014年12月18日 星期四 10时50分08秒
************************************************************************/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<cstring>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<cstdlib>
#include<ctime>
#include<set>
using namespace std;
typedef struct stu
{
int votenum;
int friendid;
int ID;
int candyneed;
bool used;
}Stu;
bool cmp_candy(const Stu& a,const Stu& b)
{
//if(a.candyneed!=b.candyneed)
return a.candyneed<b.candyneed;
}
Stu student[110];
Stu tmp[110];
inline int mapID(int ID)
{
for(int i=1;i<=100;i++) if(student[i].ID==ID) return i;
}
int main(void)
{
int T;
scanf("%d",&T);
while(T--)
{
int N;
//int maxvote=0;
scanf("%d",&N);
memset(student,0,sizeof(student));
for(int i=1;i<=N;i++)
{
student[i].ID=i;
student[i].used=false;
}
for(int i=2;i<=N;i++)
{
scanf("%d",&student[i].friendid);
student[student[i].friendid].votenum++;
}
for(int i=2;i<=N;i++)
{
scanf("%d",&student[i].candyneed);
}
//Init Complete
int needvote=student[1].votenum;
int mincandy=900000;
//Enumeration
while(needvote<=N-1)
{
int needtoget=needvote-student[1].votenum;
int toget=0; //how many votes I must get
bool fail=false;
int sumcandy=0;
for(int i=2;i<=N && !fail;i++)
{
if(student[i].votenum>=needvote)
{
toget+=student[i].votenum-needvote+1;
if(toget>needtoget)
{
fail=true;
}
}
}
//Greedy
if(!fail)
{
for(int i=2;i<=N;i++)
{
if(student[i].votenum>=needvote)
{
int getnum=student[i].votenum-needvote+1;
int cur=0;
//Find out and put all the students vote for ID=i to tmp Array
for(int j=2;j<=N;j++)
{
if(student[j].friendid==i)
{
tmp[cur++]=student[j];
}
}
sort(tmp,tmp+cur,cmp_candy);
for(int j=0;j<getnum;j++)
{
sumcandy+=tmp[j].candyneed;
student[mapID(tmp[j].ID)].used=true;
}
}
}
int cur=0;
for(int i=2;i<=N;i++)
if(!student[i].used && student[i].friendid!=1) tmp[cur++]=student[i];
if(cur)
{
sort(tmp,tmp+cur,cmp_candy);
for(int i=0;i<needtoget-toget;i++)
sumcandy+=tmp[i].candyneed;
}
if(sumcandy<mincandy) mincandy=sumcandy;
}
needvote++;
}
printf("%d\n",mincandy);
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.