PAT甲级1083.

目录

A1083

题目

样例

样例1

输入:

4
Tom CS000001 59
Joe Math990112 89
Mike CS991301 100
Mary EE990830 95
60 100

输出:

Mike CS991301
Mary EE990830
Joe Math990112

样例2

输入:

2
Jean AA980920 60
Ann CS01 80
90 95

输出:

NONE

思路和坑点

　　对学生按照成绩从高到低排序，然后遍历查询输出符合条件的学生，为了优化排序的时间，使用下标排序的方法。

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef struct node{                        //学生结构体 
    string name,id;
    int score;
}Node;
vector<Node> v;
vector<int> sid;                            //排序用的下标数组 
bool cmp(int a,int b){                      //排序函数 
    return v[a].score>v[b].score;
}
int main(void){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt","r",stdin);
#endif
    int n; scanf("%d",&n);
    v.resize(n); sid.resize(n);             //初始化结构体数组大小和下标数组大小 
    for(int i=0;i<n;i++){
        sid[i]=i;                           //初始化下标数组 
        cin>>v[i].name>>v[i].id;            //读入学生数据 
        scanf("%d",&v[i].score);
    }
    sort(sid.begin(),sid.end(),cmp);        //排序 
    int a,b,cnt=0;
    scanf("%d%d",&a,&b);                    //读取上下限，cnt用于计数 
    for(int i=0;i<n;i++){
        int k=sid[i];
        if(v[k].score>=a&&v[k].score<=b){   //如果满足要求，输出并计数 
            printf("%s %s\n",v[k].name.c_str(),v[k].id.c_str());
            cnt++;
        }
        else if(v[k].score<a) break;        //由于分数从高到低排序，所以一旦分数低于下届，结束循环 
    }
    if(cnt==0) puts("NONE");                //如果不存在给定范围内的学生，输出NONE 
    return 0;
}