【题目描述】
Elections are coming. You know the number of voters and the number of parties — n and m respectively. For each voter you know the party he is going to vote for. However, he can easily change his vote given a certain amount of money. In particular, if you give i-th voter ci bytecoins you can ask him to vote for any other party you choose.
The United Party of Berland has decided to perform a statistical study — you need to calculate the minimum number of bytecoins the Party needs to spend to ensure its victory. In order for a party to win the elections, it needs to receive strictly more votes than any other party.、
【题目链接】
http://codeforces.com/contest/1020/problem/C
【算法】
枚举答案（一号政党最终（至少）的选民数x），其它政党则最终选民数至多为x-1，贪心选取贿赂者。若一号政党仍不足x人，则从剩下的选民中贪心的取。
思想类似的题目：1、（钓鱼）https://loj.ac/problem/10009 （暴力+贪心） 2、朴素的环形均分纸牌（暴力枚举环的断点）
【代码】暴力最终选民数
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
int n,m,tot;
ll ans=LLONG_MAX;
vector<int> party[];
int rec[];
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) {
int p,c; scanf("%d%d",&p,&c);
party[p].pb(c);
}
for(int i=;i<=m;i++) sort(party[i].begin(),party[i].end());
for(int i=max(,(int)party[].size());i<=n;i++) {
int cur=party[].size(); ll cost=;
tot=;
for(int j=;j<=m;j++) {
int k;
for(k=party[j].size();k>=i;k--) cost+=party[j][party[j].size()-k],cur++;
for(k=party[j].size()-k;k<party[j].size();k++) rec[++tot]=party[j][k];
}
if(cur<i) {
sort(rec+,rec+tot+);
for(int k=;k<=tot&&cur<i;k++) cost+=rec[k],cur++;
}
ans=min(ans,cost);
}
printf("%I64d\n",ans);
return ;
}
【钓鱼】暴力最终到达的鱼塘
#include <bits/stdc++.h>
using namespace std;
int n,H,ans;
int b[],dx[],t[];
int main()
{
scanf("%d%d",&n,&H); H=H*/;
for(int i=;i<=n;i++) scanf("%d",&b[i]);
for(int i=;i<=n;i++) scanf("%d",&dx[i]);
for(int i=;i<=n;i++) scanf("%d",&t[i]),t[i]+=t[i-];
for(int i=;i<=n;i++) {
int cur=; priority_queue< pair<int,int> > pq;
for(int j=;j<=i;j++) pq.push(make_pair(b[j],dx[j]));
int T=H-t[i];
while(pq.top().first>&&T>) {
cur+=pq.top().first; T--;
pair<int,int> p=pq.top(); pq.pop();
p.first-=p.second; pq.push(p);
}
ans=max(ans,cur);
}
printf("%d\n",ans);
return ;
}