可能是晚上脑子瓦特了，我居然没有想出来。。。
题目大意：
有n个人，m个政党，每个人刚开始支持的政党是pi，你可以贿赂他ci元钱，改变他支持的政党
问你至少要花费多少使得1号政党当选。当选是要求改政党的得票严格高于其他政党
题解：
枚举一号政党当选是的选票，然后贪心
注意要判断当前方案是否可行，别用set，会多一个log
# include<iostream> # include<algorithm> # include<queue> # include<cstdio> # include<cmath> # include<vector> # include<cstring> using namespace std; typedef long long LL; const int mn = 3005; bool vis[mn]; int n,m; vector<pair<int,int> > s[mn]; vector<pair<int,int> > a; LL ans=3*1e12 + 5; int main() { int x,y; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d%d",&x,&y); s[x].push_back(make_pair(y,i)); if(x!=1) a.push_back(make_pair(y,i)); } sort(a.begin(),a.end()); int tmp=s[1].size(),N=a.size(); for(int i=1;i<=m;i++) { if(s[i].size()>=tmp) sort(s[i].begin(),s[i].end()); } for(int i=0;i<=n-tmp;i++) { // printf("%d\n",i); bool flag=true; int ret=0; long long cost=0; memset(vis,0,sizeof(vis)); for(int j=2;j<=m;j++) { int k=s[j].size(); if(k>=tmp+i) { if(k-(tmp+i)+1+ret>i) {flag=false;break;} ret+=k-(tmp+i)+1; for(int ss=0;ss<k-(tmp+i)+1;ss++) { cost+=s[j][ss].first; vis[s[j][ss].second]=1; } } } if(!flag) continue; /*for(int j=0;j<i-ret;j++) cost+=a[j];*/ if(i!=ret) { int j=0,k=0; while(1) { if(j==N) { flag=false; break; } if(!vis[a[j].second]) { cost+=a[j].first;k++; if(k==i-ret) break; } j++; } } //printf("%d %d\n",i,cost); if(flag) ans=min(ans,cost); } printf("%I64d",ans); return 0; }
原文：https://www.cnblogs.com/logeadd/p/9462430.html