[PAT解题报告] PAT Judge
简单题,就是排序问题。
n个队伍m个题目,每个队伍的每个题目有3种状态:
(1) 没提交—— 不计入总分
(2) 提交但没通过编译——不计入总分
(3) 提交通过编译得到了一个分数 [0..p], 计入总分
对队伍排名,要求:
(1) 至少提交并通过编译一个题目的队伍才出现在排名上——也就是说至少有一个情况(2)或者(3)的队伍
(2) 总分最高则排在前面,相同则完全对的题目也就是上面情况(3)越多排在前面,还相同队伍id小的排在前面
(3) 总分相同的队伍名次相同,这就需要维护一个名次值,只要出现不同的总分,才更新为( 前面总分大于他的队伍数-1)
直接做就可以了,我们可以只存必然出现在排名上的队伍,也可以把出现与否也写进cmp函数里面,最后排序的时候,一定出现在排名上的队伍排在前面。本质就是cmp函数怎么写而已。
输出注意: 没有提交的题目输出"-",
提交过的题目,编译没成功也输出0分,编译成功直接输出分数——也可能是0分,无所谓。
#include <cstdio> #include <cstring> #include <string> #include <algorithm> using namespace std; int score[10004][5]; int perfect[10004]; int total[10004]; int p[5]; int id[10004]; bool cmp(const int &x,const int &y) { if (total[x] != total[y]) { return total[x] > total[y]; } if (perfect[x] != perfect[y]) { return perfect[x] > perfect[y]; } return x < y; } int main() { int n, m, k; scanf("%d%d%d",&n,&m,&k); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { score[i][j] = -2; } } for (int i = 0; i < m; ++i) { scanf("%d",p + i); } for (int i = 0; i < k; ++i) { int x,y,z; scanf("%d%d%d",&x,&y,&z); if (z > score[--x][--y]) { score[x][y] = z; } } k = 0; for (int i = 0; i < n; ++i) { bool show = false; for (int j = 0; j < m; ++j) { if (score[i][j] >= 0) { show = true; total[i] += score[i][j]; if (score[i][j] == p[j]) { ++perfect[i]; } } } if (show) { id[k++] = i; } } sort(id, id + k, cmp); for (int i = 0, j = 0; i < k; ++i) { printf("%d %05d %d",((i == 0) || (total[id[i]] != total[id[i - 1]]))?(j = i + 1):j, id[i] + 1, total[id[i]]); for (int x = 0; x < m; ++x) { if (score[id[i]][x] >= -1) { printf(" %d",max(0, score[id[i]][x])); } else { printf(" -"); } } puts(""); } return 0; }
原题连接: http://www.patest.cn/contests/pat-a-practise/1075