zoj 3715 Kindergarten Election

本文从WordPress迁移而来, 查看全部WordPress迁移文章

枚举后贪心

题意:n个人从1到n编号,每个人可以投一票但是不能投给自己。1号是主角,想做班长,但票数必须严格大于其他人,但是主角可以任何人,收买每个人都有一个代价。求主角做到班长的最小花费。注意主角一开始没有投票,它可以选择投给任何人除开自己

思路:主角的票一定是投给当前票数最少的人,这样对他的影响最小。

另外主角最后当选班长,他拥有的票数为v的话,其他人的票数必须全部 <= v-1,如果全部人的票数<=v-1的情况下,主角的票数已经>v,那么这个枚举是失败的(因为我们是假定主角的票数确切为v),然后将其他票拉过来给主角的时候,就贪心地选。

这个题应该说不难,但是训练的时候没想出来,主要是没想到枚举主角确切得到了v票,代码注意点细节即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define N 110
#define INF 10000000
#define pb push_back
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

struct peo{
int from,to,cost;
peo(){}
peo(int f,int t,int c){
from = f; to = t; cost = c;
}
bool operator < (const peo &temp)const{
return cost < temp.cost;
}
};
vector<peo>a[N];
int n,To[N],Cost[N],vote[N],ans[N],p[N];

void solve(){
fill(ans,ans+n+5,INF);
for(int v = vote[1]; v <= n-1; v++){
int s = 0;
for(int i = 2; i <= n; i++)
if(vote[i] >= v) s += (vote[i]-(v-1));
if(vote[1] + s > v) continue;
int sum = 0;
for(int i = 2; i <= n; i++){
if(vote[i] <= v-1){ p[i] = 0; continue; }
p[i] = vote[i]-(v-1);
for(int k = 0; k < p[i]; k++)
sum += a[i][k].cost;
}
while(vote[1] + s < v){
int id,Min = INF;
for(int i = 2; i <= n; i++){
if(p[i] == a[i].size()) continue;
if(a[i][p[i]].cost < Min){
Min = a[i][p[i]].cost; id = i;
}
}
sum += Min; s++; p[id]++;
}
ans[v] = sum;
}
int res = INF;
for(int v = vote[1]; v <= n; v++)
res = min(res,ans[v]);
printf("%d\n",res);
}

int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i = 1; i <= n; i++)
a[i].clear();
cl(vote,0);
for(int i = 2; i <= n; i++){
scanf("%d",&To[i]);
vote[To[i]]++;
}
for(int i = 2; i <= n; i++)
scanf("%d",&Cost[i]);
for(int i = 2; i <= n; i++)
a[To[i]].pb(peo(i,To[i],Cost[i]));

//将1号的票投给现在票最少的人
int id,temp = INF;
for(int i = 2; i <= n; i++)
if(vote[i] < temp) id = i;
a[id].pb(peo(1,id,INF));
//将1号的票投给现在票最少的人

for(int i = 1; i <= n; i++)
sort(a[i].begin(),a[i].end());

solve();
}
return 0;
}