Codeforces Round #503 (by SIS, Div. 2) C. Elections （暴力+贪心）

【题目描述】

　　　　Elections are coming. You know the number of voters and the number of parties — $\mathrm{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[3010];
int rec[3010];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) {
        int p,c; scanf("%d%d",&p,&c);
        party[p].pb(c);
    }
    for(int i=1;i<=m;i++) sort(party[i].begin(),party[i].end());
    for(int i=max(1,(int)party[1].size());i<=n;i++) {
        int cur=party[1].size(); ll cost=0;
        tot=0;
        for(int j=2;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+1,rec+tot+1);
            for(int k=1;k<=tot&&cur<i;k++) cost+=rec[k],cur++;
        }
        ans=min(ans,cost);
    }
    printf("%I64d
",ans);
    return 0;
}

 【钓鱼】暴力最终到达的鱼塘

#include <bits/stdc++.h>
using namespace std;
int n,H,ans;
int b[110],dx[110],t[110];
int main()
{
    scanf("%d%d",&n,&H); H=H*60/5;
    for(int i=1;i<=n;i++) scanf("%d",&b[i]);
    for(int i=1;i<=n;i++) scanf("%d",&dx[i]);
    for(int i=2;i<=n;i++) scanf("%d",&t[i]),t[i]+=t[i-1];
    for(int i=1;i<=n;i++) {
        int cur=0; priority_queue< pair<int,int> > pq;
        for(int j=1;j<=i;j++) pq.push(make_pair(b[j],dx[j]));
        int T=H-t[i];
        while(pq.top().first>0&&T>0) {
            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
",ans);
    return 0;
}