算法排序5 PAT Judge

程序员文章站 2022-05-12 09:31:47

...

全部每周作业和视频思考题答案和解析见浙江大学数据结构思考题+每周练习答案

题目：The ranklist of PAT is generated from the status list, which shows the scores of the submissions. This time you are supposed to generate the ranklist for PAT.

Input Specification:

Each input file contains one test case. For each case, the first line contains 3 positive integers, N (≤10^4), the total number of users, K (≤5), the total number of problems, and M (≤10^5), the total number of submissions. It is then assumed that the user id's are 5-digit numbers from 00001 to N, and the problem id's are from 1 to K. The next line contains K positive integers p[i] (i=1, ..., K), where p[i] corresponds to the full mark of the i-th problem. Then M lines follow, each gives the information of a submission in the following format:

每个输入文件包含一个测试用例。对于每种情况，第一行包含3个正整数，N（<10^4），用户总数，K（<5），问题总数，M（<10^5），提交总数。然后假设用户id是从00001到N的5位数，问题id是从1到K的。下一行包含K个正整数p[i]（i=1，…，K），其中p[i]对应于第i个问题的完整标记。接下来是M行，每行以以下格式提供提交的信息：

user_id problem_id partial_score_obtained

where partial_score_obtained is either −1 if the submission cannot even pass the compiler, or is an integer in the range [0, p[problem_id]]. All the numbers in a line are separated by a space.

其中，如果提交甚至不能通过编译器，则获得的部分_分数为-1，或者是[0，p[problem_id]]范围内的整数。一行中的所有数字都用空格隔开。

Output Specification:

For each test case, you are supposed to output the ranklist in the following format:

rank user_id total_score s[1] ... s[K]

where rank is calculated according to the total_score, and all the users with the same total_score obtain the same rank; and s[i] is the partial score obtained for the i-th problem. If a user has never submitted a solution for a problem, then "-" must be printed at the corresponding position. If a user has submitted several solutions to solve one problem, then the highest score will be counted.

其中，排名是根据total_score计算的，所有total_score相同的用户得到相同的排名；s[i]是第i个问题得到的部分分数。如果用户从未提交问题的解决方案，则必须在相应位置打印“-”。如果用户提交了多个解决方案来解决一个问题，则将计算最高分数。

The ranklist must be printed in non-decreasing order of the ranks. For those who have the same rank, users must be sorted in nonincreasing order according to the number of perfectly solved problems. And if there is still a tie, then they must be printed in increasing order of their id's. For those who has never submitted any solution that can pass the compiler, or has never submitted any solution, they must NOT be shown on the ranklist. It is guaranteed that at least one user can be shown on the ranklist.

等级表必须按等级的非递减顺序打印。对于具有相同等级的用户，必须按照完全解决问题的个数按非递增顺序进行排序。如果仍然有平局，则必须按id的递增顺序打印它们。对于从未提交过任何可以通过编译器的解决方案或从未提交过任何解决方案的人，它们不能显示在ranklist上。可以保证至少有一个用户可以显示在ranklist上。

Sample Input:

7 4 20
20 25 25 30
00002 2 12
00007 4 17
00005 1 19
00007 2 25
00005 1 20
00002 2 2
00005 1 15
00001 1 18
00004 3 25
00002 2 25
00005 3 22
00006 4 -1
00001 2 18
00002 1 20
00004 1 15
00002 4 18
00001 3 4
00001 4 2
00005 2 -1
00004 2 0

Sample Output:

1 00002 63 20 25 - 18
2 00005 42 20 0 22 -
2 00007 42 - 25 - 17
2 00001 42 18 18 4 2
5 00004 40 15 0 25 -

解答：

首先我想说这个题目又长又讨厌。

首先想到可能应该使用基数排序算法，先准备桶，索引从0到100，然后排总成绩，然后再在每个桶里排全对的个数和名称。但是具体细节我们还是一边写一边思考吧。

然后也可以用表排序，因为每个元素要比较的东西有点多，所以要移动的东西也有点多，这个时候可能用到表排序更好一些。

然后想到一种比较猥琐的方式：写个compare函数以后用C++的sort函数进行排序，自己只需要把数据读进去就好。所以其实用什么排序方式都是可以的，比较函数写好就行了。

然后我写完程序以后，怎么提交最后都是最后一个测试答案错误，然后我就一点一点勘察。最后发现当把ID初始化为最大时，程序提交就全部正确了：

struct result4a{
	int question[6];
	int total;
	int allRightNum;
	int ID;
	int flag;
};

bool compareAB(result4a a, result4a b) {
	if (a.total > b.total)return true;
	else if (a.total < b.total)return false;
	else {
		if (a.allRightNum > b.allRightNum)return true;
		else if (a.allRightNum < b.allRightNum)return false;
		else {
			if (a.ID < b.ID)return true;
			else return false;
		}
	}
}

……

	vector<result4a> myResult(N+1);
	for (int i = 1;i<=N;i++) {
		myResult[i].ID = 1000000;  // 一定要初始化成最大的！ 
		myResult[i].allRightNum = 0;
		myResult[i].total = 0;
		myResult[i].flag = 0;
		myResult[i].question[0] = -1;

		myResult[i].question[1] = -1;
		myResult[i].question[2] = -1;
		myResult[i].question[3] = -1;
		myResult[i].question[4] = -1;
		myResult[i].question[5] = -1;
	}

这就不明白了，因为凡是没有提交的人，flag一定是0，而在后面flag是0的是不会输出的。而只要提交了东西的，就算没有编译通过，id也会被重设。但是为什么id不设置为最大的，最后一项测试的输出就是错的呢？

后来我想明白了，这是与输出 i 有关的。

比如6号和10号都是0分，6号直接没去，而10号提交但是得了0分，这个时候，6号的ID是0,10号的ID是10

在sort排序中，根据上面我们写的compare程序，会把6号放在10号的前面，然后当输出的时候，根据下面的答案，我们输出的tempi会在当tempValue不等于当前学生总分时进行更新，假设拍完序以后，假设5号总成绩是10，6号排在第12个，10号排在第16个，第12一直到第16到一直往后所有的分数都是0，而因为6号没有提交过答案，这个时候tempi不会进行更新，所以直到一直到第16个数的时候，tempi才更新为16，但是要知道10号本来应该排在第12个的，所以错误。

所以ID一定要初始化为一个最大值，例如1000000。

答案：

#include <iostream>
#include <vector>
#include<algorithm>
using namespace std;

struct result4a{
	int question[6];
	int total;
	int allRightNum;
	int ID;
	int flag;
};


bool compareAB(result4a a, result4a b) {
	if (a.total > b.total)return true;
	else if (a.total < b.total)return false;
	else {
		if (a.allRightNum > b.allRightNum)return true;
		else if (a.allRightNum < b.allRightNum)return false;
		else {
			if (a.ID < b.ID)return true;
			else return false;
		}
	}
}


int main(void) {

	int N; int K; int M;
	cin >> N >> K >> M;
	int QtotalScore[6];
	for (int i = 1;i <= K;i++) {
		cin >> QtotalScore[i];
	}
	
	vector<result4a> myResult(N+1);
	for (int i = 1;i<=N;i++) {
		myResult[i].ID = 1000000;  // 一定要初始化成最大的！ 
		myResult[i].allRightNum = 0;
		myResult[i].total = 0;
		myResult[i].flag = 0;
		myResult[i].question[0] = -1;

		myResult[i].question[1] = -1;
		myResult[i].question[2] = -1;
		myResult[i].question[3] = -1;
		myResult[i].question[4] = -1;
		myResult[i].question[5] = -1;
	}

	int stuID,qNum,qScore;
	for (int i = 0;i < M;i++) {
		cin >> stuID >> qNum >> qScore;
		myResult[stuID].ID = stuID;
		if (qScore == -1) {
			if(myResult[stuID].question[qNum] == -1)
				myResult[stuID].question[qNum] = 0;
		}
		else {
			myResult[stuID].flag = 1;
			if (myResult[stuID].question[qNum] < qScore) {
				if (myResult[stuID].question[qNum] == -1)myResult[stuID].question[qNum] = 0;
				myResult[stuID].total += qScore - myResult[stuID].question[qNum];
				myResult[stuID].question[qNum] = qScore;
				if (qScore == QtotalScore[qNum]) {
					myResult[stuID].allRightNum++;
				}
			}		
		}
	}
	
	sort(myResult.begin() + 1, myResult.end(), compareAB);

	int tempValue = myResult[1].total;
	int tempi = 1;
	for (int i = 1;i <= N;i++) {
		if (myResult[i].flag != 0) {
			if (myResult[i].total == tempValue);
			else {
				tempValue = myResult[i].total;
				tempi = i;
			}		
			printf("%d %05d %d", tempi,myResult[i].ID, myResult[i].total);
			for (int j = 1;j <= K;j++)
			{
				if (myResult[i].question[j] != -1) {
					cout << " " << myResult[i].question[j];
				}
				else {
					cout << " -";
				}
			}
			cout << endl;
		}
	}

	system("pause");
	return 0;
}

测试结果：

算法排序5 PAT Judge

算法排序5 PAT Judge

Input Specification:

Output Specification:

Sample Input:

Sample Output:

MIT算法导论公开课之第5课线性时间排序

【Algorithms公开课学习笔记5】排序算法part2——归并排序

2020-11-16 数据结构与算法（5）冒泡、选择、插入、希尔、快速、归并排序及二分法查找

用Html5实现简单选择排序算法和演示，附代码