PAT1055 The World‘s Richest 不同STL对用时的影响

亦凉 2022-12-01 03:41 81阅读 0赞

这题关键在于不能在每次query时排序或建优先队列，而应该先排好，再想方法输出对应年龄段的人。  
此题query对时间的影响最大，着重点应该是降低query用时。  
之前也听闻过priority\_queue的STL实现很慢，经过这题看来不应该使用priority\_queue来降低用时。

# 直接排序+string #

#include <bits/stdc++.h>
    using namespace std;
    const int maxn=100100;
    int n,m,k;
    struct Per{ 
        string name;
        //char name[10];
        int age,worth;
    }p[maxn];
    bool cmp(const Per& a,const Per& b){ 
        return a.worth!=b.worth?a.worth>b.worth:a.age!=b.age?a.age<b.age:a.name<b.name;//strcmp(a.name,b.name)<0;
    };
    int main(){ 
    #ifdef ONLINE_JUDGE
    #else
        freopen("../1.txt","r",stdin);
    #endif
        cin>>n>>m;
        //scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++){ 
            cin>>p[i].name>>p[i].age>>p[i].worth;
            //scanf("%s%d%d",p[i].name,&p[i].age,&p[i].worth);
        }
        sort(p,p+n,cmp);
        int amin,amax;
        for(int j=1;j<=m;++j) { 
            cin >> k >> amin >> amax;
            //scanf("%d%d%d",&k,&amin,&amax);
            int cnt = 0;
            printf("Case #%d:\n", j);
            for (int i = 0; i < n; i++) { 
                if (p[i].age >= amin && p[i].age <= amax) { 
                    cout << p[i].name << ' ' << p[i].age << ' ' << p[i].worth << endl;
                    //printf("%s %d %d\n",p[i].name,p[i].age,p[i].worth);
                    cnt++;
                    if(cnt>=k)break;
                }
            }
            if (cnt == 0)puts("None");
        }
        return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoZXJwYWh1_size_16_color_FFFFFF_t_70_pic_center]  
只差一点就超时了，这种写法最简单

# 直接排序+char字符串 #

#include <bits/stdc++.h>
    using namespace std;
    const int maxn=100100;
    int n,m,k;
    struct Per{ 
        //string name;
        char name[10];
        int age,worth;
    }p[maxn];
    bool cmp(const Per& a,const Per& b){ 
        return a.worth!=b.worth?a.worth>b.worth:a.age!=b.age?a.age<b.age:strcmp(a.name,b.name)<0;
    };
    int main(){ 
    #ifdef ONLINE_JUDGE
    #else
        freopen("../1.txt","r",stdin);
    #endif
        //cin>>n>>m;
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++){ 
            //cin>>p[i].name>>p[i].age>>p[i].worth;
            scanf("%s%d%d",p[i].name,&p[i].age,&p[i].worth);
        }
        sort(p,p+n,cmp);
        int amin,amax;
        for(int j=1;j<=m;++j) { 
            //cin >> k >> amin >> amax;
            scanf("%d%d%d",&k,&amin,&amax);
            int cnt = 0;
            printf("Case #%d:\n", j);
            for (int i = 0; i < n; i++) { 
                if (p[i].age >= amin && p[i].age <= amax) { 
                    //cout << p[i].name << ' ' << p[i].age << ' ' << p[i].worth << endl;
                    printf("%s %d %d\n",p[i].name,p[i].age,p[i].worth);
                    cnt++;
                    if(cnt>=k)break;
                }
            }
            if (cnt == 0)puts("None");
        }
        return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoZXJwYWh1_size_16_color_FFFFFF_t_70_pic_center 1]

# 使用vector存储索引再对索引vector排序+每个年龄段只保留100个防超时(大表->小表) #

#include <bits/stdc++.h>
    using namespace std;
    const int maxn=100100;
    int n,m,k;
    struct Per{ 
        string name;
        int age,worth;
    }p[maxn];
    int ages[500];
    bool cmp(int a,int b){ 
        return p[a].worth!=p[b].worth?p[a].worth>p[b].worth:p[a].age!=p[b].age?p[a].age<p[b].age:p[a].name<p[b].name;
    };
    int main(){ 
    #ifdef ONLINE_JUDGE
    #else
        freopen("../1.txt","r",stdin);
    #endif
        vector<int>allIdx,smallIdx;
        cin>>n>>m;
        for(int i=0;i<n;i++){ 
            cin>>p[i].name>>p[i].age>>p[i].worth;
            allIdx.push_back(i);
        }
        sort(allIdx.begin(),allIdx.end(),cmp);
        for(int i:allIdx){ 
            if(ages[p[i].age]<100){ 
                smallIdx.push_back(i);
                ages[p[i].age]++;
            }
        }
        int amin,amax;
        for(int i=1;i<=m;++i) { 
            cin >> k >> amin >> amax;
            int cnt = 0;
            printf("Case #%d:\n", i);
            for (int i = 0; i < smallIdx.size() && cnt < k; i++) { 
                if (p[smallIdx[i]].age >= amin && p[smallIdx[i]].age <= amax) { 
                    cout << p[smallIdx[i]].name << ' ' << p[smallIdx[i]].age << ' ' << p[smallIdx[i]].worth << endl;
                    cnt++;
                }
            }
            if (cnt == 0)puts("None");
        }
        return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoZXJwYWh1_size_16_color_FFFFFF_t_70_pic_center 2]

由于每个query最多输出M个人，M最大值为100，所以每个年龄段最多只用存100个人  
这么倒一次比较精妙

# (超时)索引排序+char字符串 #

之前一直以为vector的效率还行，但没想到排序倒腾了一次后也会超时，这一个新的认识，之前做pat都没有遇到仅由vector导致的超时。

#include <bits/stdc++.h>
    using namespace std;
    const int maxn=100100;
    int n,m,k;
    struct Per{
        //string name;
        char name[10];
        int age,worth;
    }p[maxn];
    int ages[500];
    bool cmp(int a,int b){
        return p[a].worth!=p[b].worth?p[a].worth>p[b].worth:p[a].age!=p[b].age?p[a].age<p[b].age:strcmp(p[a].name,p[b].name)<0;
    };
    int main(){
    #ifdef ONLINE_JUDGE
    #else
        freopen("../1.txt","r",stdin);
    #endif
        vector<int>allIdx,smallIdx;
        //cin>>n>>m;
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++){
            //cin>>p[i].name>>p[i].age>>p[i].worth;
            scanf("%s%d%d",p[i].name,&p[i].age,&p[i].worth);
            allIdx.push_back(i);
        }
        sort(allIdx.begin(),allIdx.end(),cmp);
        int amin,amax;
        for(int j=1;j<=m;++j) {
            //cin >> k >> amin >> amax;
            scanf("%d%d%d",&k,&amin,&amax);
            int cnt = 0;
            printf("Case #%d:\n", j);
            for (int i = 0; i < n; i++) {
                if (p[allIdx[i]].age >= amin && p[allIdx[i]].age <= amax) {
                    //cout << p[allIdx[i]].name << ' ' << p[allIdx[i]].age << ' ' << p[allIdx[i]].worth << endl;
                    printf("%s %d %d\n",p[allIdx[i]].name,p[allIdx[i]].age,p[allIdx[i]].worth);
                    cnt++;
                    if(cnt>=k)break;
                }
            }
            if (cnt == 0)puts("None");
        }
        return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoZXJwYWh1_size_16_color_FFFFFF_t_70_pic_center 3]

# (超时)索引排序+string #

也超时代码我就不贴了

# (超时)优先队列控制最多输出个数 #

这种做法无论用char数组还是string数组都超时  
用优先队列是我想多了

## char字符串 ##

#include <bits/stdc++.h>
    using namespace std;
    const int maxn=100010;
    int n,m,k;
    vector<int>ages[1010];
    struct Stu{ 
        //string name;
        char name[10];
        int age,worth;
    }stu[maxn];
    struct cmp{ 
        bool operator()(int a,int b){ 
            return stu[a].worth!=stu[b].worth?stu[a].worth>stu[b].worth:stu[a].age!=stu[b].age?stu[a].age<stu[b].age:strcmp(stu[a].name,stu[b].name)<0;
        }
    };
    int main(){ 
    #ifdef ONLINE_JUDGE
    #else
        freopen("../1.txt","r",stdin);
    #endif
        //cin>>n>>m;
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;++i){ 
            //cin>>stu[i].name>>stu[i].age>>stu[i].worth;
            scanf("%s%d%d",stu[i].name,&stu[i].age,&stu[i].worth);
            ages[stu[i].age].push_back(i);
        }
        for(int i=1;i<=m;++i){ 
            printf("Case #%d:\n",i);
            int amin,amax,outputs;
            //cin>>outputs>>amin>>amax;
            scanf("%d%d%d",&outputs,&amin,&amax);
            amin=max(amin,0);
            amax=min(amax,201);
            priority_queue<int,vector<int>,cmp>q;
            for(int age=amin;age<=amax;++age){ 
                for(int idx:ages[age]){ 
                    q.push(idx);
                    if(q.size()>outputs&&!q.empty())q.pop();
                }
            }
            if(q.empty()){ 
                puts("None");
                continue;
            }
            vector<int>index;
            while (!q.empty()){ 
                index.push_back(q.top());
                q.pop();
            }
            for(auto it=index.rbegin();it!=index.rend();it++){ 
                int idx=*it;
                //cout<<stu[idx].name<<' '<<stu[idx].age<<' '<<stu[idx].worth<<endl;
                printf("%s %d %d\n",stu[idx].name,stu[idx].age,stu[idx].worth);
            }
        }
        return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoZXJwYWh1_size_16_color_FFFFFF_t_70_pic_center 4]

## string字符串 ##

#include <bits/stdc++.h>
    using namespace std;
    const int maxn=100010;
    int n,m,k;
    vector<int>ages[1010];
    struct Stu{ 
        string name;
        int age,worth;
    }stu[maxn];
    struct cmp{ 
        bool operator()(int a,int b){ 
            return stu[a].worth!=stu[b].worth?stu[a].worth>stu[b].worth:stu[a].age!=stu[b].age?stu[a].age<stu[b].age:stu[a].name<stu[b].name;
        }
    };
    int main(){ 
    #ifdef ONLINE_JUDGE
    #else
        freopen("../1.txt","r",stdin);
    #endif
        cin>>n>>m;
        for(int i=0;i<n;++i){ 
            cin>>stu[i].name>>stu[i].age>>stu[i].worth;
            ages[stu[i].age].push_back(i);
        }
        for(int i=1;i<=m;++i){ 
            printf("Case #%d:\n",i);
            int amin,amax,outputs;
            cin>>outputs>>amin>>amax;
            amin=max(amin,0);
            amax=min(amax,201);
            priority_queue<int,vector<int>,cmp>q;
            for(int age=amin;age<=amax;++age){ 
                for(int idx:ages[age]){ 
                    q.push(idx);
                    if(q.size()>outputs&&!q.empty())q.pop();
                }
            }
            if(q.empty()){ 
                puts("None");
                continue;
            }
            vector<int>index;
            while (!q.empty()){ 
                index.push_back(q.top());
                //int idx=q.top();
                //cout<<stu[idx].name<<' '<<stu[idx].age<<' '<<stu[idx].worth<<endl;
                q.pop();
            }
            for(auto it=index.rbegin();it!=index.rend();it++){ 
                int idx=*it;
                cout<<stu[idx].name<<' '<<stu[idx].age<<' '<<stu[idx].worth<<endl;
            }
            /*sort(index.begin(),index.end(),cmp()); for(int idx:index){ cout<<stu[idx].name<<' '<<stu[idx].age<<' '<<stu[idx].worth<<endl; }*/
        }
        return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoZXJwYWh1_size_16_color_FFFFFF_t_70_pic_center 5]

# 部分排序(partial\_sort)替代优先队列没写出来，但我感觉这样应该也不行 #

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoZXJwYWh1_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/924e5369fd6342e9944fdd3d01e4dce3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoZXJwYWh1_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/946ade2a97a745059bae9c79cd250177.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoZXJwYWh1_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/48186ee50f0f412a95e7a6ac8d20c62d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoZXJwYWh1_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/875d2dbca372457a9c06ad4f574c823c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoZXJwYWh1_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221123/e74efa30349b43b3b57b62d49803f62a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoZXJwYWh1_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221123/5440d55fa03e4547a1632b9f4596d363.png