CCF认证201909-4推荐系统

原题链接

CCF认证201909-4推荐系统

解题思路

错误思路

  理解清楚题意再做题,这是前提啊。刚开始读题的时候不明白下面这句话的意思。刚开始我的理解是。每个商品按分数从高到低选出ki个商品。我用vector< set<node> > data(m);存放商品的学校。其中data[i]对应i类商品的所有小类商品的编号和分数。最后选择的时候是从0遍历到m-1类商品,每类商品取出不超过ki个小类商品。其实这样的思路是错的啊。。应该是所有的商品按分数由高到低依次排序,然后选取输出。并要求每一类商品的个数不超过指定的阈值。
  这个很挫的想法,最后只拿了十分。我实在想不明白为啥超时只给十分。原来是我的思路出错了。要看清题目啊看清题目。血泪教训!
在这里插入图片描述

正确题解
1、重新编号

  由大类的商品类号和商品的编号,共同确定了一个商品。因为再增加和删除操作时,都需要通过类号和编号来确定需要操作的商品,为了查找的方便,同时也为了减小时间的开销,我们将类号和编号组合形成新的id号,以此来作为商品的唯一标识。具体的做法是id = 类号*10^9 + 编号

2、set容器实现自动排序

  涉及到增加和删除的操作,商品的内容时不断发生变化的,每次操作后都调用sort进行排序显然是有大问题的。因此在这里就需要借助stl容器来确保有序。很显然set是绝佳的选择。因为是自定义的数据类型,因此需要重载运算符,规定排序的规则。也就是下面的代码

    bool operator <(const node& s) const{
        if(score != s.score){
            return score > s.score;
        }else{
            return id < s.id;
        }
    } 
3、辅助数据结构记录商品位置

  进行删除操作时,给定类号和编号(也就相当于id),为了找到该商品,需要遍历容器,然后再删除。显然这绝对是卡时间的地方。做法是用unordered_map<long long, set<node>::iterator> um;来记录对应商品在set中的位置。只要根据编号,就可以快速删除指定的商品。(set容器在执行insert函数时,是有返回值的。是pair,第一个就是迭代器的位置,第二个是bool类型,表示插入是否成功)

代码

#include <bits/stdc++.h>
using namespace std;
struct node{
    long long id;
    long long score;
    node(long long i,long long s){
        id = i;
        score = s;
    }
    bool operator <(const node& s) const{
        if(score != s.score){
            return score > s.score;
        }else{
            return id < s.id;
        }
    } 
};
long long m,n,opt,tid,ts,k;
int t,type;
int main(){
    const long long mul = (long long)(1e9);
    scanf("%lld",&m);
    scanf("%lld",&n);
    vector<int> K(m);  //存储每类商品被选中的最多件数
    set<node> data;//用户数据
    unordered_map<long long, set<node>::iterator> um;  //存储商品id和对应的set中的迭代器
    //初始化数据 
    for(int i=0;i<n;i++){
        scanf("%lld",&tid);
        scanf("%lld",&ts);
        for(int j = 0; j < m;j++){
            long long a = j*mul + tid;
            um[a] = data.insert(node{a,ts}).first;
        } 
    }
    scanf("%lld",&opt);
    for(int i=0;i<opt;i++){
        cin>>t;
        if(t == 1){//增加 
            cin>>type>>tid>>ts;
            long long a = type*mul + tid;
            um[a] = data.insert(node{a,ts}).first;
        }else if(t == 2){//删除 
            cin>>type>>tid;
            long long a = type*mul + tid;
            data.erase(um[a]);
            um.erase(a);
        }
        else if(t == 3){//查询 
            vector<vector<int> > ans(m);
            cin >> k;
            for (int i = 0; i < m; ++i)
                cin >> K[i];
            for (auto& i : data) {  //遍历整个set
                t = i.id / mul;
                if (ans[t].size() < K[t]) {
                    ans[t].push_back(i.id % mul);
                    if (--k == 0)  //商品已选满k件,结束遍历
                        break;
                }
            }
            for (auto& i : ans)
                if (i.empty()) {  //没有选中的商品,输出-1
                    cout << "-1\n";
                } else {
                    for (auto j : i)
                        cout << j << " ";
                    cout << "\n";
                }
        }   
    }
    return 0;
}
Tags:

Add a Comment

邮箱地址不会被公开。