PAT甲级 1129 Recommendation System 25分 set和结构体操作符重载

「爱情、让人受尽委屈。」 2023-07-22 09:25 3阅读 0赞

来源：[https://pintia.cn/problem-sets/994805342720868352/problems/994805348471259136][https_pintia.cn_problem-sets_994805342720868352_problems_994805348471259136]

# 题解 #

见[liuchuo][]

# 满分版本 #

#include<iostream>
    #include<set>
    #include<algorithm>
    using namespace std;
    int book[50001];
    struct node{
        int value,cnt;
        bool operator < (const node &a) const{
            return (cnt != a.cnt) ? cnt > a.cnt : value < a.value;
        }
    };
    int main(){
        int n,m,x;
        scanf("%d %d",&n,&m);
        set<node> s;
        for(int i=1;i<=n;i++){
            scanf("%d",&x);
            if(i!=1){
                printf("%d:",x);
                int tempCnt=0;
                for(auto it=s.begin();tempCnt<m&&it!=s.end();it++){
                    printf(" %d",it->value);
                    tempCnt++;
                }
                printf("\n");
            }
            auto it=s.find(node{x,book[x]});
            if(it!=s.end()){
                s.erase(it);
            }
            book[x]++;
            s.insert(node{x,book[x]});
        }
        return 0;
    }

# 超时版本 #

报错都是超时错误。50000的数据量，拷贝很多次会超时。

//16/25分
    struct node{
        int no,times=0;
    };
    bool cmp(node &a,node &b){
        return a.times==b.times?a.no<b.no:a.times>b.times;
    }
    int main(){
        int n,m,x;
        scanf("%d %d",&n,&m);
        vector<node> v(n+1);
        for(int i=1;i<=n;i++){
            scanf("%d",&x);
            vector<node> vt(v);
            sort(vt.begin(),vt.end(),cmp);
            if(i!=1){
                printf("%d:",x);
                if(i<=m){
                    for(int j=0;j<i-1;j++){
                        printf(" %d",vt[j].no);
                    }
                }else{
                    for(int j=0;j<m;j++){
                        printf(" %d",vt[j].no);
                    }
                }
                printf("\n");
            }
            v[x].no=x;
            v[x].times++;
        }
        return 0;
    }

[https_pintia.cn_problem-sets_994805342720868352_problems_994805348471259136]: https://pintia.cn/problem-sets/994805342720868352/problems/994805348471259136
[liuchuo]: https://www.liuchuo.net/archives/3848