CodeForces-1020 C-Elections(欲張り+列挙)

タイトル:
党派きょうそう投票
n人がいて、m人がいて、このn人は一人一人が投げたい党派の番号Piを持っていて、この人が彼の考えを変えるには、Ci元が必要です.
今あなたは1番の党派です.もしあなたが勝つために(あなたの票数は他の党派の票数より厳格です)、最も少ないお金はいくらですか.
考え方:
一人一人を支出の小さい順に並べて、0からnまでの列挙で勝つために必要な票を挙げて、すべての投票する人を遍歴して、もし彼が投票する党派の票が現在の列挙の票より大きいならば、この人の票を買ってきて、最後にすべての費用の中で最小のそれを取ることができます.
爆int......
コード:

#include 
#include 
using namespace std;
const int maxn = 3005;
int n,m;
struct Voter{
    int p;
    long long c;
}v[maxn];
int vis[maxn],hav[maxn];
map<int,int> mp;

bool cmp(Voter a,Voter b){
    return a.c<b.c;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0; i){
        scanf("%d%lld",&v[i].p,&v[i].c);
        mp[v[i].p]++;//               
    }
    sort(v,v+n,cmp);
    long long c=0,ans=1e18;
    for(int i=0; i<=n; i++){
        int num=mp[1];
        c = 0;
        memset(vis,0,sizeof(vis));
        memset(hav,0,sizeof(hav));
        for(int j=0; j){
            if(v[j].p==1) {vis[j]=1;continue;}
            if(mp[v[j].p]-hav[v[j].p]>i){//         
                c += v[j].c;
                vis[j] = 1;
                hav[v[j].p]++;
                num++;
            }
        }
        for(int j=0; j//                      （    ）
            if(num>i) break;
            if(vis[j]) continue;
            c+=v[j].c;
            num++;
        }
        ans = min(ans,c);
    }
    printf("%lld
",ans);
    return 0;
}

 
転載先:https://www.cnblogs.com/sykline/p/10455293.html