PAT甲级1055.

目录

A1055

题目

样例

输入:

12 4
Zoe_Bill 35 2333
Bob_Volk 24 5888
Anny_Cin 95 999999
Williams 30 -22
Cindy 76 76000
Alice 18 88888
Joe_Mike 32 3222
Michael 5 300000
Rosemary 40 5888
Dobby 24 5888
Billy 24 5888
Nobody 5 0
4 15 45
4 30 35
4 5 95
1 45 50

输出:

Case #1:
Alice 18 88888
Billy 24 5888
Bob_Volk 24 5888
Dobby 24 5888
Case #2:
Joe_Mike 32 3222
Zoe_Bill 35 2333
Williams 30 -22
Case #3:
Anny_Cin 95 999999
Michael 5 300000
Alice 18 88888
Cindy 76 76000
Case #4:
None

思路和坑点

　　排序，然后按照要求查找并输出，为了不超时，尽可能的少使用stl，并且快速排序使用排下标的方式实现。

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef struct node{
    string id;
    int age,w;
}Node;
Node v[100005];
int sid[100005];
bool cmp(int i,int j){
    if(v[i].w!=v[j].w) return v[i].w>v[j].w;
    else if(v[i].age!=v[j].age) return v[i].age<v[j].age;
    else return v[i].id<v[j].id;
}
int main(void){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt","r",stdin);
#endif
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++){
        sid[i]=i;
        cin>>v[i].id;
        scanf("%d%d",&v[i].age,&v[i].w);
    }
    sort(sid,sid+n,cmp);
    for(int i=1;i<=k;i++){
        printf("Case #%d:\n",i);
        int num,st,ed,cnt=0;
        scanf("%d%d%d",&num,&st,&ed);
        for(int j=0;j<n;j++){
            int index=sid[j];
            if(v[index].age>=st&&v[index].age<=ed){
                cnt++;
                printf("%s %d %d\n",v[index].id.c_str(),v[index].age,v[index].w);
            }
            if(cnt==num) break;
        }
        if(cnt==0) puts("None");
    }
    return 0;
}