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;
	int grade;
};

bool cmp(const Student &s1, const Student &s2) {
	return s1.grade > s2.grade;
}

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)
		indexes[students[i].grade] = 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 注意点:

如果出题人稍微设置点陷阱, 那么就是在grade1和grade2上面, 不保证grade1 < grade2. 那么我们就要自己加逻辑去处理.

Written on July 16, 2014