PAT甲级-1075 Judge

题目

题目大意

对参加PAT考试的考生进行排名。输入给出人数N，题目数量K，提交总次数M。接下来一行给出每道题对应的分数。考生的提交按照考生id-题目序号-本次提交的分数格式给出。

注意，如果提交的结果编译器未通过，那么给定的分数会是-1，但是该考生该题所得的分数为0。

排序按照总分数>得满分的题目总数>id 的优先级。如果一个考生没有可以通过编译器的提交或者没有任何提交，那么这个考生不参与排名。参与排名的考生，没有提交过的题目输出“-”，提交但编译不通过的就输出0，提交并通过的就输出相应的分数。

思路

首先想到的就是用结构体将id，各题分数，排名，总分，得满分的题目数量捆绑在一起。各题分数可以用一个int数组，因为N、M的范围都比较大，而K的范围<=5，所以不会占用太多内存空间。

我觉得题目最关键的就是对“0”、“-1”、“-”这几种情况的处理，用什么把这几种情况区分开来，反正用total是很难直接区分的。我把score[6]数组初始化为-1，如果某个用户没有任何提交或者提交的编译器不通过，那么从score[1]到score[5]的和一定是-5，这样就可以把不参与排名的人排除掉，而剩下的就是参与排名的人。之前说过题意，参与排名的人提交但不通过编译器，得分还是0，所以要加一个flag数组，看每个题是做过但没通过编译还是压根就没做过，再来个for循环遍历，将做过但没通过编译的题目分数从-1改成0。

这里我又在结构体中加了一个total2，total2是不管flag数组的，是为了排除不参与排名的人设置的，total2 = -5 时，就可以把这个人删了。total则是计算总分数的。total计算完后排序，再按照题意输出就ok了。

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;struct stu{int id;int score[6];  // 从1开始存储分数int flag[6];  // 每道题目有没有写int total;  // 题目中要求的总分数int total2;  // 如果是-5则不参与排序int num;  // 得满分的题目的数量int rank;
};
vector<stu> v(10003);bool cmp(stu x, stu y){if (x.total == y.total){if (x.num == y.num){return x.id < y.id;}return x.num > y.num;}return x.total > y.total;
}int main(){int n, k, m;cin >> n >> k >> m;vector<int> t(k + 1);  // 题目for (int i = 1; i <= k; i++){cin >> t[i];}for (int i = 1; i <= n; i++){for (int j = 1; j <= 6; j++){v[i].score[j] = -1;}}  // 初始化scorefor (int i = 0; i < m; i++){int id, tid, score;cin >> id >> tid >> score;v[id].id = id;v[id].score[tid] = max(score, v[id].score[tid]);v[id].flag[tid] = 1;}for (int i = 1; i <= n; i++){for (int j = 1; j < 6; j++){if (v[i].flag[j] == 1){v[i].total += v[i].score[j];}v[i].total2 += v[i].score[j];if (v[i].score[j] == t[j]){v[i].num++;}}if (v[i].total2 == -5){v.erase(v.begin() + i);i--;n--;}}  // 筛选出参与排序的人for (int i = 1; i <= n; i++){for (int j = 1; j <= k; j++){if (v[i].score[j] == -1 && v[i].flag[j] == 1){v[i].score[j] = 0;v[i].total++;}}}  // 只要参与排名，即使有一道题提交为-1，这个题分数也为0sort(v.begin() + 1, v.begin() + n + 1, cmp);v[1].rank = 1;for (int i = 1; i <= n; i++){if (i == 1){cout << "1" << " ";}else{v[i].total == v[i-1].total ? v[i].rank = v[i-1].rank : v[i].rank = i;cout << v[i].rank << " ";}printf("%05d %d ", v[i].id, v[i].total);for (int j = 1; j <= k; j++){if (v[i].flag[j] == 1){cout << v[i].score[j];}else{cout << "-";}if (j != k){cout << " ";}}cout << endl;}return 0;
}