J-夺宝奇兵

思路:看着题比较晚了,一看woc这不就是CF原题嘛,考虑枚举最终票数。枚举完票数就开始处理,把每个党超过这个票数且收钱最少的人收买过来,如果这些人都收买完了可是还没有达到预定的票数,就一直收买之前还没有收买过的学生直到人数达标,就这样巴拉巴拉A了

#include<stdio.h>
#include<bits\stdc++.h>
using namespace std;
typedef long long ll;
int n,m,ns,cnt[3005],Sum[3005];
struct peo{
    int p,c,rk;
}a[3005];
struct val{
    int rk,v;
}b[3005];
bool vis[3005];
ll min_ans=-1,ans;
bool cmpa (peo a,peo b){
    if(a.p==b.p) return a.c<b.c;
    return a.p<b.p;
}
bool cmpb (val a,val b){
    return a.v<b.v;
}
int main(){
    scanf("%d%d",&m,&n);
    for (int i=1;i<=n;++i){
        scanf("%d%d",&a[i].c,&a[i].p);
        a[i].p++;
        a[i].rk=i;
        b[i].rk=i;
        b[i].v=a[i].c;
    }
    sort(a+1,a+1+n,cmpa);
    sort(b+1,b+1+n,cmpb);
    for (int i=1;i<=n;++i)
        Sum[ a[i].p ]++;
    for (int s=1;s<=n;++s){
        ns=0;
        ans=0;
        memset(vis,0,sizeof(vis));
        memset(cnt,0,sizeof(cnt));
        for (int j=1;j<=n;++j){
            if(a[j].p==1) ns++,vis[ a[j].rk ]=true;
            else{
                if(Sum[ a[j].p ]-cnt[ a[j].p ]>=s){
                    vis[ a[j].rk ]=true;
                    cnt[ a[j].p ]++;
                    ans+=a[j].c;
                    ns++;
                }
            }
        }
        for (int i=1;i<=n;++i){
            if(ns>=s) break;
            if(vis[ b[i].rk ]) continue;
            ns++;
            ans+=b[i].v;
        }
        if(min_ans==-1) min_ans=ans;
        min_ans=min(ans,min_ans);
    }
    cout<<min_ans;
    return 0;
}