201909-4. 推荐系统.md

【CCF CSP-20190904】推荐系统

算法设计

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

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

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

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

C++代码

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
struct Commodity {  //商品类
    long long id, score;  // id和分数
    Commodity(long long i, long long s) : id(i), score(s) {}
    bool operator<(const Commodity& c) const {  //重载小于运算符
        return this->score != c.score ? this->score > c.score : this->id < c.id;
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    const long long mul = (long long)(1e9);
    gg m, n, id, score, op, t, c, k;
    cin >> m >> n;
    vector<gg> K(m);  //存储每类商品被选中的最多件数
    set<Commodity> commodities;  //对所有商品进行排序
    unordered_map<long long, set<Commodity>::iterator> um;  //存储商品id和对应的set中的迭代器
    for (gg i = 0; i < n; ++i) {
        cin >> id >> score;
        for (gg j = 0; j < m; ++j) {
            long long a = j * mul + id;
            um[a] = commodities.insert(Commodity(a, score)).first;
        }
    }
    cin >> op;
    while (op--) {
        cin >> c;
        if (c == 1) {  //添加商品
            cin >> t >> id >> score;
            long long a = t * mul + id;
            um[a] = commodities.insert(Commodity(a, score)).first;
        } else if (c == 2) {  //删除商品
            cin >> t >> id;
            long long a = t * mul + id;
            commodities.erase(um[a]);
            um.erase(a);
        } else {
            vector<vector<gg>> ans(m);
            cin >> k;
            for (gg i = 0; i < m; ++i)
                cin >> K[i];
            for (auto& i : commodities) {  //遍历整个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 {
                    sort(i.begin(), i.end());  //从小到大排序
                    for (auto j : i)
                        cout << j << " ";
                    cout << "\n";
                }
        }
    }
    return 0;
}

让人无语的是，上面的代码提交之后只有 60 分，我想了两个小时也没找到错误的地方。令人尴尬的是，当我注释掉第 56 行用来对要输出的商品进行排序的代码后，提交竟然拿到了满分。但是题目中的确是要求对输出的每类商品编号从小到大排序的，注释掉 56 行代码，输出的每类商品编号就是先按得分从大到小输出，再按编号从小到大输出的了。所以我觉得有可能是后台评测数据有问题。如果有遇到类似疑惑的小伙伴可以在评论区讨论一下。附上满分的代码（其实只是注释掉了上面代码的第 56 行）：

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
struct Commodity {  //商品类
    long long id, score;  // id和分数
    Commodity(long long i, long long s) : id(i), score(s) {}
    bool operator<(const Commodity& c) const {  //重载小于运算符
        return this->score != c.score ? this->score > c.score : this->id < c.id;
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    const long long mul = (long long)(1e9);
    gg m, n, id, score, op, t, c, k;
    cin >> m >> n;
    vector<gg> K(m);  //存储每类商品被选中的最多件数
    set<Commodity> commodities;  //对所有商品进行排序
    unordered_map<long long, set<Commodity>::iterator> um;  //存储商品id和对应的set中的迭代器
    for (gg i = 0; i < n; ++i) {
        cin >> id >> score;
        for (gg j = 0; j < m; ++j) {
            long long a = j * mul + id;
            um[a] = commodities.insert(Commodity(a, score)).first;
        }
    }
    cin >> op;
    while (op--) {
        cin >> c;
        if (c == 1) {  //添加商品
            cin >> t >> id >> score;
            long long a = t * mul + id;
            um[a] = commodities.insert(Commodity(a, score)).first;
        } else if (c == 2) {  //删除商品
            cin >> t >> id;
            long long a = t * mul + id;
            commodities.erase(um[a]);
            um.erase(a);
        } else {
            vector<vector<gg>> ans(m);
            cin >> k;
            for (gg i = 0; i < m; ++i)
                cin >> K[i];
            for (auto& i : commodities) {  //遍历整个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 {
                    // sort(i.begin(), i.end());  //从小到大排序
                    for (auto j : i)
                        cout << j << " ";
                    cout << "\n";
                }
        }
    }
    return 0;
}