Codeforces Round落503(by SIS,Div.2)C.Elections(欲張り)

1957 ワード

テーマリンク:http://codeforces.com/contest/1020/problem/C
 
意味記述:
有権者はn人で、mの政党はあります。  (n、m<=3000)、i番目の有権者は2 pi、ci(pi<=m、ci<=1 e 9)を持っていて、政党piに投票すると表していますが、ci金貨を与えると、彼の投票対象は政党1(政党番号1からm)に変わります。
政党の1票が最も多く、必要最小限の金貨数が求められている。
テーマ分析:
この問題は最初に二分間をとりたいですが、ちょうど一番高い点数を獲得できる時に使う金貨を答えにしましたが、二点は間違っています。
例えばサンプル:
5      (5人の有権者、5つの政党)2 100  (1日の有権者投票2日の政党は、100円のお金がかかります。1号政党に投票できます。)3 200 4,300 5,800 5,900
ちょうど最高票を獲得できるのは2(4番と1番を買う)です。
しかし、1番2番3番を買ったら、同じように一番高い点数を得られます。
正解:
枚挙政党1で(1からnまで)得票数に必要な金貨は、得票数が最も高い場合には最小にすればいいです。
コード:
#include
#define INF 0x3f3f3f3f3f3f3f3f
#define ll long long
using namespace std;
int n,m,x,y;
vectorv[3005];
ll cal(int k){
    vectorbk;
    ll res = 0;
    ll cnt = v[1].size();//  1    
    for(int i = 2;i <= m;i++){
        int num=v[i].size();
        for(int j = 0; j < num;j++){
            if(num-j >= k){ //num-j   i     ,           k,        1   
                res += v[i][j];
                cnt++;
            }else bk.push_back(v[i][j]);    //          
        }
    }
    if(cnt < k){  //    1           k 
        sort(bk.begin(),bk.end());//                 
        for(int i = 0; i < bk.size() && cnt < k;i++){
            res += bk[i];
            cnt++;
        }
    }
    return res; //   k    n,       k,        
}
int main(){
    while(~scanf("%d %d",&n,&m)){
        for(int i = 1;i <= m;i++)v[i].clear();
        for(int i = 1;i <= n;i++){
            scanf("%d %d",&x,&y);
            v[x].push_back(y);
        }
        for(int i = 1;i <= m;i++){//             
            sort(v[i].begin(),v[i].end());
        }
        ll ans=INF;
        for(int k=1;k<=n;k++){   //    1     
            ans=min(ans,cal(k)); //     1  k ,       k ,       
        }
        printf("%lld
",ans); } return 0; }