zoj 3715

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

想法： 枚举1号当班长后所得的票数k，其他人的票数应该小于等于k-1，多的按费用从小到大进行收买， 如果还是不够K，将剩余的票按费用小到大的顺序收买。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int N=110;
const int INF=99999999;
struct node{int to,pr;bool operator<(const node no)const{return pr<no.pr;}
}f[N];
vector<int>G[N];
int vis[N];	
int n;
void init(){for(int i=0;i<N;i++) G[i].clear();
}
int operate(int k){int now=G[1].size();int ans=0,i,j,g=0;memset(vis,0,sizeof(vis));for(i=2;i<=n;i++)if(G[i].size()>k){for(j=0;G[i].size()-j>k;j++) {ans+=f[G[i][j]].pr;vis[G[i][j]]=1;now++;}}else g=1;if(now<g+k+1){for(i=0;now<g+k;i++) if(!vis[i]&&f[i].to!=1) ans+=f[i].pr,now++;}return ans;
}
int main(){int t,i;scanf("%d",&t);while(t--){init();scanf("%d",&n);for(i=0;i<n-1;i++) scanf("%d",&f[i].to);for(i=0;i<n-1;i++) scanf("%d",&f[i].pr);sort(f,f+n-1);for(i=0;i<n-1;i++) G[f[i].to].push_back(i);int ans=INF;for(i=max((int)G[1].size()-1,0);i<=n;i++) ans=min(ans,operate(i));printf("%d\n",ans);	 }
}

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

---