題意：
? ? ? 有n個小朋友競選班長，一號想當(dāng)班長，每個人都必須選擇一個人當(dāng)班長，并且不可以選擇自己，并且每個人都有一個權(quán)值ai，這個權(quán)值就是如果1想讓這個人改變主意選擇自己當(dāng)班長就得給他ai個糖果，只有當(dāng)1的票數(shù)是唯一最多的時候，1才能競選班長，問1競選班長的最小花費糖果數(shù)。

思路

? ? ? 昨天練習(xí)賽的最后一個題，今天才AC，這個題目我們可以用貪心的方法，記得當(dāng)時自己看完也馬上感覺是貪心，可以因為選擇了錯誤的貪心方法和策略，導(dǎo)致寫了很長，而且越寫越蒙，最后寫的腦袋短路了，悲劇啊，說下正解，我們可以枚舉1號競選時的票數(shù),對于每一次枚舉，如果當(dāng)前有人的票數(shù)比1號的x多，那么就把他減少到x-1（肯定是挑選費用最小的）,然后把當(dāng)前的票數(shù)加到1身上，最后如果1號的票數(shù)大于當(dāng)前的枚舉票數(shù)，枚舉失敗，如果等于，那么就更新最優(yōu)值，如果小于，就在剩下的沒有選則1的里面挑選幾個最小的補上去，這樣就行了，說到這，可能有人去會想，1不是也要投一票嗎，怎么沒考慮，其實根本不用管1這票投給了誰，因為只有出現(xiàn)這樣的狀態(tài)這一票才會有影響x x-1 x-1 x-1 x-1.....但是這個狀態(tài)是不存在的，想一下，這個題目每個人最多投一票，如果1的票數(shù)為x，那么那個狀態(tài)的總票數(shù)就是 x + (x - 1) * (n - 1) + 1,其實x是大于等于2的(這個地方自己想，很好想)，那么就會得到 2 + （2 - 1） * （n - 1）+ 1 = n + 2,而每個人都一票，總票數(shù)是n，所以矛盾，所以不存在那種狀態(tài)，所以不用考慮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\n" ,min);
? ?}
? ?return 0;
}?
? ? ? ? ?

總結(jié)

以上是生活随笔為你收集整理的ZOJ3715 竞选班长求最小花费的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。