推荐系统

这道题主要是它通过一个map数组对每一类的物品进行排序，pair< int,int > 第一个为score,第二个为-id.
负号是因为取rbegin的时候正好是最小的id在前，然后从每个pair数组里面都取出min(k,ki)个物品放到vector中
以val为第一关键字，id为第二关键字，就ok了

我ccf上是满分 这里差了两个点（现在好像也能过了） 可以到ccf去交 http://118.190.20.162/view.page?gpid=T91

#include<bits/stdc++.h>
using namespace std;
const int N = 3e4+7, M = 57;
int m,n, cnt[M];
map<pair<int,int>,int > mp1[M];
map<int,int > mp2[M];
vector<int> ans[M];
struct ppp{
    int cla,id,val;
};
int cmp(ppp a, ppp b){
    if(a.val!=b.val) return a.val>b.val;
    else{
        if(a.cla!=b.cla) return a.cla<b.cla;
        else if(a.id!=b.id) return a.id<b.id;
    }
}
int main(){
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>m>>n;
    for(int i=0;i<n;i++){
        int id, score;
        cin>>id>>score;
        for(int j=0;j<m;j++){
            mp1[j][make_pair(score,-id)] = 1;
            mp2[j][id] = score;
        }
    }
    int q, op, x, y, z, k;
    cin>>q;
    vector<ppp> v;
    while(q--){
        cin>>op;
        if(op==1){
            cin>>x>>y>>z;
            mp1[x][make_pair(z,-y)] = 1;
            mp2[x][y] = z;
        }
        else if(op==2){
            cin>>x>>y;
            mp1[x].erase(make_pair(mp2[x][y],-y));
            mp2[x].erase(y);
        }
        else{
            v.clear();
            cin>>k;
            for(int i=0;i<m;i++) cin>>cnt[i];
            for(int u=0;u<m;u++){
                int j=0,x=0;
                for(map<pair<int,int>,int >::reverse_iterator i = mp1[u].rbegin();j<k&&x<cnt[u]&&i!=mp1[u].rend();i++){
                    pair<int,int> p = i->first;
                    ppp tmp; tmp.id = -p.second, tmp.val = p.first, tmp.cla = u;
                    //cout<<tmp.id<<' '<<tmp.val<<'\n';
                    v.push_back(tmp);
                    j++, x++;
                }
            }
            sort(v.begin(),v.end(),cmp);
            for(int i=0;i<m;i++) ans[i].clear();
            for(int i=0;i<min(k,(int)v.size());i++){
                ppp pp = v[i];
                ans[pp.cla].push_back(pp.id);
            }
            for(int i=0;i<m;i++){
                if(ans[i].size()==0) cout<<-1<<'\n';
                for(int j=0;j<ans[i].size();j++){
                    cout<<ans[i][j];
                    cout<<(j==ans[i].size()-1?'\n':' '); 
                }
            }
        }
    }
}