PAT 甲级 1129 Recommendation System (25 point(s)) set自动排序

不念不忘少年蓝@ 2024-05-08 06:14 10阅读 0赞

##### 题目 #####

[题目链接][Link 1]

##### 思路 #####

题目大意：给一个人的选座记录，根据用户以往选择座位的次数来为推荐k个座位，按照选择的次数从大往小推荐，如果次数一样则按id从小到大排序  
做法：定义一个结构体，利用set自动排序的特性，每次取前几个元素。更新元素时，需要删除之后再插入

##### 代码 #####

# include<iostream>
    # include<set>
    
    using namespace std;
    
    const int maxn = 50010;
    
    struct item {
        
         int id, cnt;
         //重载小于号
         bool operator < (const item& obj) const {
        
              return cnt != obj.cnt ? cnt > obj.cnt : id < obj.id;
         }
    };
    
    set<item> s;
    
    int n, k, x;
    int book[maxn];
    
    int main(){
        
         scanf("%d%d", &n, &k);
         for(int i = 0; i < n; i ++) {
        
              scanf("%d", &x);
              //判断是不是第一个
              if(i) {
        
                   printf("%d:", x);
                   int j = 0;
                   for(auto it = s.begin(); it != s.end() && j < k; ++it, ++j)
                        printf(" %d", it -> id);
                   printf("\n");
              }
              //set不能更改，只能删除
              if(book[x]) s.erase({
        x, book[x]});
              ++book[x];
              s.insert({
        x, book[x]});
         }
         system("pause");
         return 0;
    }

[Link 1]: https://pintia.cn/problem-sets/994805342720868352/problems/994805348471259136

发表评论取消回复

表情：

评论列表（有 0 条评论，10人围观）

还没有评论，来说两句吧...

相关阅读

相关 PAT 甲级 1129 Recommendation System (25 point(s)) set自动排序

题目题目链接思路题目大意：给一个人的选座记录，根据用户以往选择座位的次数来为推荐k个座位，按照选择的次数从大往小推荐，如果次数一样则按id从小到大排序做法：定义一个结构体...

不念不忘少年蓝@/ 2024年05月08日 06:14/ 0 赞/ 11 阅读

相关 PAT 甲级 1113 Integer Set Partition (25point(s)) 双指针

题目题目链接思路题目大意：给一堆数，将这堆数分成两份，要保证两份数的个数至多差一个，且各自和的差值最大；将这堆数从小到大排序，一个指针i指向首元素，一个指针j指向尾元素，...

雨点打透心脏的1/2处/ 2024年05月08日 06:06/ 0 赞/ 8 阅读

相关 PAT（甲级）1118 Birds in Forest (25point(s))

题目题目链接思路题目大意：在同一张照片里的鸟属于一个树，所以用并查集就可以做了；至于鸟的数量，可以通过set去重存储；代码#include <iostream&gt...

迈不过友情╰/ 2024年05月08日 06:02/ 0 赞/ 7 阅读

相关 PAT（甲级）1021 Deepest Root (25point(s))

题目题目链接思路题目大意：给一张图，这个图有点特殊，没有环且边数等于节点数-1，即是一棵树；每个节点都可能是根节点，要求是输出那些作为根节点时树的深度最大的节点；首先要判...

桃扇骨/ 2024年05月08日 06:01/ 0 赞/ 10 阅读

相关 PAT（甲级）1047 Student List for Course (25point(s))

题目题目链接思路题目大意：给出每个人所选的科目，要求按科目输出选择的人有哪些；先来分析一下，我们肯定需要为每个科目开一个数组，存储有哪些人选择了这个科目，但有个问题，名字...

港控/mmm°/ 2024年05月08日 06:00/ 0 赞/ 8 阅读

相关 PAT（甲级）1024 Palindromic Number (25point(s))

题目题目链接思路题目大意：判断一个字符串是不是回文串，如果不是可以翻转后相加在判断是不是回文串；本质是大数相加问题，大数相加需要先把数字翻转一下，将个位数字放到数组的第0...

悠悠/ 2024年05月08日 06:00/ 0 赞/ 9 阅读

相关 PAT（甲级）1078 Hashing (25point(s))

题目题目链接思路先判断原题hash位置有没有被占用，如果被占用，就进行二次平方探查；代码#include <iostream>#include <str...

阳光穿透心脏的1/2处/ 2024年05月08日 05:59/ 0 赞/ 7 阅读

相关 PAT（甲级）1101 Quick Sort (25point(s))

题目题目链接思路题目大意：判断一个数字是否大于他左边的任何数字且小于他右边的任何数字；先把每个数字左边的最大值和右边的最小值统计出来，分别用left 和 right 数组...

﹏ヽ暗。殇╰゛Y/ 2024年05月08日 05:53/ 0 赞/ 9 阅读

相关 1129. Recommendation System （25）

Recommendation system predicts the preference that a user would give to an item. Now you

「爱情、让人受尽委屈。」/ 2022年05月28日 11:47/ 0 赞/ 111 阅读

相关 (1129) Recommendation System 排序

Recommendation system predicts the preference that a user would give to an item. Now you

谁借莪１个温暖的怀抱￠/ 2022年03月18日 06:51/ 0 赞/ 134 阅读