CCF 201909-4 推荐系统

算法设计

　　由于我们需要选出得分最大的K件商品，得出相同的先按类号从小到大排序，再按编号从小到大排序。那么我们可以将所有商品放入到一个set变量bbt中进行自动排序。另外，同类商品编号必然不同，不同类商品编号可能相同，所以我们可以用类号+编号来唯一标识一件商品。由于商品的编号在10^9 以内，而类号在以内，我们可以用类号∗109+编号 类号*10^9+编号类号∗10 ^9+编号来作为一件商品唯一的id，显然每件商品和其id是一一对应的。这样的id可以用long long类型存储，且按id从小到大排序就相当于题目要求的“先按类号从小到大排序，再按编号从小到大排序”的排序原则。如果我们得到一件商品的id，那么这件商品的类号=id/10^9,编号=id%10^9 。

　　于是我们可以定义一个商品类dat，其中定义两个成员变量：id和score。为了方便set排序，需要在类内重载<运算符，保证商品先按得分从大到小排序，再按id从小到大排序。但是这又需要考虑另一个问题，题目中需要对商品进行添加和删除，添加和删除操作都是通过商品的id来操作的，我们显然无法在set中我们需要给出id和score两个变量才能查找到一件商品，而无法只通过商品的id查找到相应的商品。怎么办呢？我们可以另外定义一个unordered_map变量um，键存储商品的id，值存储指向这件商品在set中的位置的迭代器。还记得set中进行插入的insert函数吗？其实这个函数是有返回值的，只不过我们不常用。它的返回值是一个pair，first成员就是指向新插入的元素在set中位置的迭代器，second成员是一个bool表示这次插入操作是否成功。于是我们在向set中插入商品时可以直接通过代码um[a] = bbt.insert(dat(a, score)).first;完成um和bbt的同步更新。进行删除时，我们先通过um找到商品在set中的迭代器，然后利用set的erase函数进行删除，另外别忘了同步对um中的对应元素也进行删除就可以了。

　　然后是打印操作，我们可以定义一个变量k存储要选出的最多商品总数，定义一个数组变量K存储每类商品被选中的最多件数，定义一个二位数组变量ans存储每类商品要输出的编号。遍历整个set，假设当前遍历到的商品所属类别为t，而ans[t][0]< K[t]，表示当前类别还没有选满，则将当前商品的编号加入到ans[t][]中，另外令变量k递减1，判断k是否变为了0，如果k变为了0，表示商品总数已选够，即可直接结束遍历。

最后，题目中要求，同类商品的编号从小到大输出，需要对ans中每类商品编号排序再输出即可。

　　然而60分之后的数据有问题，如要获得满分，请注释掉第55行用来对要输出的商品进行排序的代码

#pragma GCC optimize(3,"Ofast","inline")
#include<set>
#include<vector>
#include<stdio.h>
#include<tr1/unordered_map>
using namespace std;
using namespace tr1;
typedef long long ll;
const ll mul=1e9;
const int M=55;
const int Kn=105;
struct dat{
    ll id;int s;
    dat(ll id=0,int s=0):id(id),s(s){}
    bool operator <(const dat &c) const{
        return s!=c.s?s>c.s:id<c.id;
    }
};
set<dat>bbt; unordered_map<ll,set<dat>::iterator>um;
int K[M],ans[M][Kn];
int main(){
    int n,m,cas,opt,t,id,s,k;
    scanf("%d%d",&m,&n);
    for(int i=0;i<n;i++){
        scanf("%d%d",&id,&s);
        for(int j=0;j<m;j++){
            ll a=j*mul+id;
            um[a]=bbt.insert(dat(a,s)).first; 
        }
    }
    for(scanf("%d",&cas);cas--;){
        scanf("%d",&opt);
        if(opt==1){
            scanf("%d%d%d",&t,&id,&s);
            ll a=t*mul+id;
            um[a]=bbt.insert(dat(a,s)).first;
        }
        else if(opt==2){
            scanf("%d%d",&t,&id);
            ll a=t*mul+id;
            bbt.erase(um[a]);um.erase(a);
        }
        else{
            scanf("%d",&k);
            for(int i=0;i<m;i++) scanf("%d",&K[i]),ans[i][0]=0;
            for(auto &i:bbt){
                t=i.id/mul;
                if(ans[t][0]<K[t]){
                    ans[t][++ans[t][0]]=i.id%mul;
                    if(!--k) break;
                }
            }
            for(int i=0;i<m;i++){
                if(!ans[i][0]){puts("-1");continue;}
//                sort(ans[i]+1,ans[i]+ans[0]+1)‘‘
                for(int j=1;j<=ans[i][0];j++) printf("%d ",ans[i][j]);
                puts("");
            }
        }
    }
    return 0;
}