# PAT 解题报告 1083. List Grades (25)

### 1083. List Grades 题目描述：

Given a list of N student records with name, ID and grade. You are supposed to sort the records with respect to the grade in non-increasing order, and output those student records of which the grades are in a given interval. It is guaranteed that all the grades are distinct. 保证所有的分数都不同, 要求降序输出在指定分数区间内的学生的姓名和id.

### 1083. List Grades 算法分析：

（1）最简单的就是直接模拟, 先给所有学生按照分数降序排序, 然后遍历学生, 如果分数在指定的分数区间里面就输出. 时间复杂度O(NlogN)

（2）第一种方法没有利用所有分数都保证不同这个特性, 这个提示其实很明显, 就是要我们使用Hash, 构造一个有101的位置的数组下标表示对应的分数从0到100都有可能, 因为分数一定不一样, 于是只要线性遍历学生列表, 把对应分数的学生插入到Hash表中即可, 然后遍历从分数grade1到grade2, 常数时间就可以从Hash表中得到每一个整数分数对应的是哪个学生, 下面是可以AC的源代码, 包括了两种算法的实现：

```#include <string>
#include <iostream>
#include <vector>
#include <algorithm>

struct Student {
std::string name;
std::string id;
};

bool cmp(const Student &s1, const Student &s2) {
}

void gao1(std::vector<Student> &students, int g1, int g2) {
bool empty = true;
std::sort(students.begin(), students.end(), cmp);
for (int i = 0; i < students.size(); ++i) {
if (students[i].grade >= g1 && students[i].grade <= g2) {
std::cout << students[i].name << ' ' << students[i].id << std::endl;
empty = false;
}
}
if (empty)
std::cout << "NONE" << std::endl;
}

void gao2(std::vector<Student> &students, int g1, int g2) {
int indexes[105];
std::fill(indexes, indexes + 105, -1);

int len = students.size();
for(int i = 0; i < len; ++i)

bool empty = true;
for(int i = g2; i >= g1; --i) {
int idx = indexes[i];
if (idx != -1) {
std::cout << students[idx].name << ' ' << students[idx].id << std::endl;
empty = false;
}
}
if (empty)
std::cout << "NONE" << std::endl;
}

int main()
{
int n;
std::vector<Student> students;

std::cin >> n;
students.resize(n);
for (int i = 0; i < n; ++i) {
std::cin >> students[i].name >> students[i].id >> students[i].grade;
}
int g1, g2;
std::cin >> g1 >> g2;

// gao1(students, g1, g2);
gao2(students, g1, g2);
return 0;
}
```

### 1083. List Grades 注意点：

Written on July 16, 2014