浙江大学数据结构MOOC-课后习题-第十讲-排序5 PAT Judge【未完成】

题目汇总
浙江大学数据结构MOOC-课后习题-拼题A-代码分享-2024

题目描述

这段文字是关于如何生成PAT（一种编程能力测试）的排行榜的说明。下面是这段文字的中文翻译：

输入说明：
每个输入文件包含一个测试案例。对于每个案例，第一行包含三个正整数，N（不超过10^4） ，表示用户总数；K（不超过5），表示问题的总数；M（不超过10^5），表示提交的总数。假定用户ID是5位数的数字，从00001到N，问题ID是从1到K。接下来的一行包含K个正整数，其中每个数字p[i]表示第i个问题的最高分数。然后是M行，每行提供一次提交的信息，格式如下：
user_id problem_id partial_score_obtained
其中partial_score_obtained是以下两种情况之一：如果提交不能通过编译器，则为-1；或者是一个整数，在[0, p[problem_id]]范围内。一行中的所有数字由空格分隔。

输出说明：
对于每个测试案例，需要按照以下格式输出排行榜：
rank user_id total_score s[1] ... s[K]
其中rank是按照total_score计算的排名，如果total_score相同，则获得相同的rank；total_score是用户的总分数；s[i]是用户在第i个问题上获得的部分分数。如果用户从未提交过针对某个问题的解决方案，或者该解决方案没有通过编译器，则相应位置打印"-"。如果用户针对一个问题提交了多个解决方案，则只计算最高分数。排行榜必须按照排名的非递减顺序打印。如果排名相同，用户必须根据完全解决问题的数量按递减顺序排序。如果仍然有平局，则必须按照他们的ID递增顺序打印。那些从未提交过可以通过编译器的解决方案，或者从未提交过任何解决方案的用户，将不会出现在排行榜上。保证至少有一个用户会出现在排行榜上。

代码展示

做不动了…还有一天就要关闭答题咯，等后面有机会再完善吧:( sad

/*
	利用多关键字排序的思想：
	先按分数排顺序
	然后按照解决问题的数量来排序
	最后按照ID来排序
*/

#include <iostream>
#include <string>
#define neverSubmit -1
#define MAX_PROBLEM 6
#define MAX_USERS 10001
#define MAX_SUBMITS 100000
/* 输入信息 */
//struct inputInfo
//{
//	std::string user_id;
//	int problem_id;
//	int partial_score_obtained;
//};
/* 用户个人信息 */
struct userInfo
{	
	int rank = -1;						/* 排名 */
	std::string user_id;				/* ID */
	int nSolve = 0;						/* 完全解决问题的数量 */
	int score[MAX_PROBLEM] = {-1, -1, -1, -1, -1}; /* 每道题得分情况-存储历史最大得分 -1表示未提交/未通过编译 */
	int sumScore;					/* 总分 */
	userInfo* Next = NULL;
	userInfo* Pre = NULL;
};
/* 表头数组类型 */
struct bucket
{
	userInfo* First = NULL;
	userInfo* Last = NULL;
};
/* 获取个位数字 */
int getLow(int score)
{
	return score % 10;
}
/* 获取十位数字 */
int getMid(int score)
{
	int temp = score / 10;
	return temp % 10;
}
/* 获取百位数字 */
int getHigh(int score)
{
	return score / 100;
}
/* 获取用户信息 */
void getUserInfo(int N, int K, int M, int P[], userInfo user[])
{	
	std::string user_id;
	int problem_id;
	int partial_score_obtained;
	/* 统计每位用户每道题所得最高分 */
	for (int i = 0; i < M; i++)
	{
		std::cin >> user_id >> problem_id >> partial_score_obtained;
		int id = std::stoi(user_id);
		user[id].user_id = user_id;
		/* 将输入的信息存于用户个人信息中 */
		if (partial_score_obtained >= 0 && partial_score_obtained <= P[problem_id])
		{
			/* 如果本次提交大于最大值则更新 */
			int maxScore = user[id].score[problem_id];
			if (partial_score_obtained > maxScore)
				user[id].score[problem_id] = partial_score_obtained;
		}
	}
	/* 计算每位用户所得总分 和 完全解决的问题个数 */
	for (int i = 1; i <= N; i++)
	{	
		user[i].sumScore = 0;
		user[i].nSolve = 0;
		for (int j = 1; j <= K; j++)
		{	
			if (user[i].score[j] != -1)
			{
				user[i].sumScore += user[i].score[j];
				if (user[i].score[j] == P[j])
					user[i].nSolve++;
			}

		}
	}
}
/* 复制用户信息 */
void copy(userInfo* SRC, userInfo* ORI, int K)
{
	SRC->rank = ORI->rank;
	SRC->sumScore = ORI->sumScore;
	SRC->user_id = ORI->user_id;
	for (int i = 0; i < K; i++)
		SRC->score[i] = ORI->score[i];
}
/* 按照分数进行基数排序 */
void scoreSort(int N, int K, int P[], userInfo user[], bucket highScoreArray[])
{
	/* 先对分数由高到低排序 基数：10 */
	bucket lowScoreArray[9];
	/* 低位排序 */
	for (int i = 1; i <= N; i++)
	{	/* low取值范围0到9 */
		int low = getLow(user[i].sumScore);
		/* 存进对应桶的末尾 */
		userInfo* newNode = (userInfo*)malloc(sizeof(userInfo));
		newNode->rank = user[i].rank;
		newNode->sumScore = user[i].sumScore;
		newNode->user_id = user[i].user_id;
		for (int i = 0; i < K; i++)
			newNode->score[i] = user[i].score[i];
		/*copy(newNode, &user[i], K);*/
		newNode->Next = NULL;
		newNode->Pre = NULL;
		/* 表头不为空且仅有一个元素 */
		if (lowScoreArray[low].First && lowScoreArray[low].First == lowScoreArray[low].Last)
		{	
			lowScoreArray[low].First->Next = newNode;
			newNode->Pre = lowScoreArray[low].First;
			lowScoreArray[low].Last = newNode;
		}
		/* 表不为空且不止一个元素 */
		else if(lowScoreArray[low].First && lowScoreArray[low].First != lowScoreArray[low].Last)
		{
			lowScoreArray[low].Last->Next = newNode;
			newNode->Pre = lowScoreArray[low].Last;
			lowScoreArray[low].Last = newNode;
		}
		/* 表为空 */
		else
		{	
			lowScoreArray[low].First = newNode;
			lowScoreArray[low].Last = newNode;
			newNode->Pre = NULL;
		}
		
	}
	/* 中位排序 */
	bucket midScoreArray[9];
	/* 按顺序从lowScoreArray中取出元素 */
	userInfo* newNode = lowScoreArray[0].First;
	int count = 0;
	int j = 0;
	while(count != N)
	{
		while(newNode == NULL && j < 9)
			newNode = lowScoreArray[++j].First; /* 找到第一个不为空的表头 */
		/* 从lowScoreArray中取出元素 */
		/* 表头不为空且仅有一个元素 */
		if (lowScoreArray[j].First != NULL && lowScoreArray[j].First == lowScoreArray[j].Last )
			lowScoreArray[j].First = lowScoreArray[j].Last = NULL;
		/* 若表中不止一个元素 */
		else if(lowScoreArray[j].First != NULL && lowScoreArray[j].First != lowScoreArray[j].Last)
			lowScoreArray[j].First = newNode->Next;
		
		count++;/* 统计排序的元素个数 */
			
		/* 存进对应桶的末尾 */
		int mid = getMid(newNode->sumScore);	/* 获取第二位置的值 */
		newNode->Next = NULL;
		newNode->Pre = NULL;
		/* 表头不为空且仅有一个元素 */
		if (midScoreArray[mid].First && midScoreArray[mid].First == midScoreArray[mid].Last)
		{
			midScoreArray[mid].First->Next = newNode;
			newNode->Pre = midScoreArray[mid].First;
			midScoreArray[mid].Last = newNode;
		}
		/* 表不为空且不止一个元素 */
		else if (midScoreArray[mid].First && midScoreArray[mid].First != midScoreArray[mid].Last)
		{
			midScoreArray[mid].Last->Next = newNode;
			newNode->Pre = midScoreArray[mid].Last;
			midScoreArray[mid].Last = newNode;
		}
		/* 表为空 */
		else
		{
			midScoreArray[mid].First = newNode;
			midScoreArray[mid].Last = newNode;
			newNode->Pre = NULL;
		}
		newNode = newNode->Next;	
	}

	/* 高位排序 */
	/* 按顺序从lowScoreArray中取出元素 */
	newNode = midScoreArray[0].First;
	count = 0;
	j = 0;
	while (count != N)
	{
		while (newNode == NULL && j < 9)
			newNode = midScoreArray[++j].First; /* 找到第一个不为空的表头 */
		/* 从midScoreArray中取出元素 */
		/* 表头不为空且仅有一个元素 */
		if (midScoreArray[j].First != NULL && midScoreArray[j].First == midScoreArray[j].Last)
			midScoreArray[j].First = midScoreArray[j].Last = NULL;
		/* 若表中不止一个元素 */
		else if (midScoreArray[j].First != NULL && midScoreArray[j].First != midScoreArray[j].Last)
			midScoreArray[j].First = newNode->Next;

		count++;/* 统计排序的元素个数 */

		/* 存进对应桶的末尾 */
		int high = getHigh(newNode->sumScore);	/* 获取第二位置的值 */
		newNode->Next = NULL;
		newNode->Pre = NULL;
		/* 表头不为空且仅有一个元素 */
		if (highScoreArray[high].First && highScoreArray[high].First == highScoreArray[high].Last)
		{
			highScoreArray[high].First->Next = newNode;
			newNode->Pre = midScoreArray[high].First;
			highScoreArray[high].Last = newNode;
		}
		/* 表不为空且不止一个元素 */
		else if (highScoreArray[high].First && highScoreArray[high].First != highScoreArray[high].Last)
		{
			highScoreArray[high].Last->Next = newNode;
			newNode->Pre = midScoreArray[high].Last;
			highScoreArray[high].Last = newNode;
		}
		/* 表为空 */
		else
		{
			highScoreArray[high].First = newNode;
			highScoreArray[high].Last = newNode;
		}
		newNode = newNode->Next;
	}
}
/* 获取排名 */
void getRank(int N, bucket scoreArray[])
{	
	/* 按顺序从scoreArray中读取元素 */
	int i = 9;
	bool flag = false;
	userInfo* preNode = NULL;
	userInfo* newNode = NULL;
	int preIndex;
	/* 找到最后一个节点 */
	for (newNode = scoreArray[i].Last; i >= 0;)
	{
		if (flag == false && newNode == NULL)
		{
			newNode = scoreArray[--i].Last;
		}
		else
		{	
			preNode = newNode;
			preIndex = i;
			break;
		}
	}
	/* 排序 */
	flag = false;
	int preRank; 
	int preScore;
	int count = 0;
	newNode = preNode;
	while(count <= N)
	{	
		/* 检查当前节点是否为空 */
		while (newNode == NULL)
		{	
			if (preIndex > 0)
			{
				newNode = scoreArray[--preIndex].Last;
			}
			else return;
		}
		/* 对第一个元素特殊处理 */
		if (flag == false)
		{
			newNode->rank = 1;
			preRank = 1;
			preScore = newNode->sumScore;
			flag = true;
			count++;
			newNode = newNode->Pre;
		}
		else
		{	/* 总分相同，则排名相同 */
			if (newNode->sumScore == preScore)
			{
				newNode->rank = preRank;
				count++;
				newNode = newNode->Pre;
			}
			/* 总分更低，则排名根据前面的人数更新 */
			else if (newNode->sumScore < preScore)
			{
				newNode->rank = ++count;
				preScore = newNode->sumScore;
				newNode = newNode->Pre;
			}
		}
	}

}
/* 根据解决问题数量再排序一次 */
void nSolveSort(int N, int K, bucket userArray[], bucket problemSolveArray[])
{
	/* k + 1个桶: 0到K */
	/* 基数：K + 1 */
	int i;
	int count = 0;
	bool flag = false;	/* flag为false表示此时为第一次排序 */
	userInfo* newNode = userArray[0].First;
	userInfo* nextNode;
	for (i = 0; i < 10; ) //i代表分数桶的数量
	{		
		/* 跳到下一个非空桶 */
		while (flag == true && newNode == NULL)
		{
			newNode = userArray[++i].First;
		}
		/* 找到第一个节点 */
		while (flag == false && newNode == NULL)
		{
			newNode = userArray[++i].First;
		}
		nextNode = newNode->Next;
		newNode->Pre = NULL;
		newNode->Next = NULL;
		flag = true;
		/* 根据解决问题数将其放到对应桶 */
		int numSolve = newNode->nSolve;
		/* 目标桶为空 */
		if (problemSolveArray[numSolve].First == NULL)
		{
			problemSolveArray[numSolve].First = newNode;
			problemSolveArray[numSolve].Last = newNode;
		}
		/* 目标桶仅有一个元素 */
		else if (problemSolveArray[numSolve].First != NULL && problemSolveArray[numSolve].First == problemSolveArray[numSolve].Last)
		{
			problemSolveArray[numSolve].First->Next = newNode;
			newNode->Pre = problemSolveArray[numSolve].First;
			problemSolveArray[numSolve].Last = newNode;
		}
		/* 目标桶不止一个元素 */
		else
		{
			problemSolveArray[numSolve].Last->Next = newNode;
			newNode->Pre = problemSolveArray[numSolve].Last;
			problemSolveArray[numSolve].Last = newNode;
		}
		newNode = nextNode;
	}
}

void printUserInfo(int K, int P[], userInfo* curUser)
{
	int i;
	std::cout << curUser->rank;
	std::cout << ' ' << curUser->user_id;
	for (i = 0; i < K; i++)
	{
		if (curUser->score[i] == -1)
			std::cout << ' ' << '-';
		else
			std::cout << ' ' << curUser->score[i];
	}
}
/* 输出最终信息 */
void output(int N, int K, int P[], bucket problemSolveArray[])
{
	int count = 0;
	int i = MAX_PROBLEM;
	bool flag = false;
	userInfo* curNode = problemSolveArray[i].First;
	while (count <= N && i >= 0)
	{	
		/* 跳到下一个非空桶末尾 */
		while (flag == true && curNode == NULL)
		{
			curNode = problemSolveArray[++i].Last;
		}
		/* 找到第一个输出的节点 */
		while (flag == false && curNode == NULL)
		{
			curNode = problemSolveArray[--i].Last;
		}
		flag = true;
		printUserInfo(K, P, curNode);
		count++;
		curNode = curNode->Pre;
	}
}
/* 根据用户ID再排一次序 */
void idSort(int N, int K, bucket problemSolveArray[])
{
	/* 用户ID */
}
int main()
{
	int N, K, M;	/* N:用户总数 K：问题总数 M：提交总数*/
	int P[MAX_PROBLEM];
	userInfo user[MAX_USERS];	/* 存储用户信息 */
	bucket scoreArray[10];
	bucket problemSolveArray[MAX_PROBLEM + 1];
	/* 初始化-读取输入 */
	std::cin >> N >> K >> M;
	for (int i = 1; i <= K; i++)
		std::cin >> P[i];
	/* 统计用户信息 */
	getUserInfo(N, K, M, P, user);
	/* 按照分数进行基数排序 */
	scoreSort(N, K, P, user, scoreArray);
	/* 获取排名 */
	getRank(N, scoreArray);
	/* 根据解决问题数量再排序一次 */
	nSolveSort(N, K, scoreArray, problemSolveArray);
	/* 输出 */
	output(N, K, P, problemSolveArray);

	return 0;
}