题目大意
现在有 n 个人, m 个党派, 第 i 个人开始想把票投给党派 pi, 而如果想让他改变他的想法需要花费 ci 元. 你现在是党派 1, 问你最少花多少钱使得你的党派得票数大于其它任意党派.
分析
我们枚举 i, 表示除了自己之外的其它任何党派最多得票数不超过 i, 而我们每次只需要改变一个党派中需要花费的钱最少的那几个人就行了, 在保证其它党派德比得票数都小于 i 之后如果自己党派的得票小于 i, 则不断改变需花费钱最少的那一个人的想法就行了. 详见代码.
代码
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<string>
- #include<algorithm>
- #include<cctype>
- #include<cmath>
- #include<cstdlib>
- #include<queue>
- #include<ctime>
- #include<vector>
- #include<set>
- #include<map>
- #include<stack>
- using namespace std;
- #define li long long
- const li inf = 1e18;
- struct node {
- int a;
- li b;
- };
- node d[5000];
- inline bool cmp(const node x,const node y){
- return x.b<y.b;
- }
- int used[5000],tot[5000];
- int main(){
- int n,m,i,j,k;
- scanf("%d%d",&n,&m);
- for(i=1;i<=n;i++){
- scanf("%d%lld",&d[i].a,&d[i].b);
- }
- sort(d+1,d+n+1,cmp);
- li ans=inf;
- for(i=1;i<=n;i++){
- memset(used,0,sizeof(used));
- memset(tot,0,sizeof(tot));
- li sum=0;
- for(j=n;j>0;j--)
- if(d[j].a!=1){
- if(tot[d[j].a]+1>=i){
- tot[1]++;
- used[j]=1;
- sum+=d[j].b;
- }else {
- tot[d[j].a]++;
- }
- }else {
- tot[1]++;
- used[j]=1;
- }
- for(j=1;j<=n;j++)
- if(!used[j]&&tot[1]<i){
- tot[1]++;
- sum+=d[j].b;
- }
- if(tot[1]>=i)ans=min(ans,sum);
- }
- cout<<ans<<endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2724909.html