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

不念不忘少年蓝@ 2024-05-08 06:14 82阅读 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