题目链接https://pintia.cn/problem-sets/994805342720868352/problems/994805393241260032
只能说题不难,但就是坑很多,不得不说cy出的这些题真是。。。。
思路大家都能想出来,就记录下几个坑点,是自己debug了以后还是没想出来上网查的。
(1)排好序后,先排除不参与排名的user
因为如果未去掉不参与排名的,比如3号从未提交,4号提交了但总分是0,因为3、4号总分是一样的,所以4号会上去找上一个有效的排名数last_r
,但这个last_r
并不是3号的排名!(3号根本不参与)
这里给一个测试用例
5 2 5
10 10
1 1 10
1 2 10
2 1 10
2 2 5
4 1 0
正确输出应该为
1 00001 20 10 10
2 00002 15 10 5
3 00004 0 0 -
4号的排名应该是3而不是2,因为他总分比上一名低。而3号根本不参与排名。
所以先预处理,把不参与排名的都去掉最保险。而这种情况只会出现在总分为0的位置,也就是列表的最末尾,所以从最末尾开始遍历,碰到总分大于0的就break
即可
for (int i = ppl.size() - 1; i >= 0; i--) {
if (ppl[i].ttl > 0)
break;
else {
if (!ppl[i].flag)
ppl.erase(ppl.begin() + i, ppl.begin() + i + 1);
}
}
输出时可以放心使用last_r
int last_r = 1;
for (int i = 0; i < ppl.size(); i++) {
// output rank
if (i == 0)
printf("1 ");
else {
if (ppl[i].ttl == ppl[i - 1].ttl)
printf("%d ", last_r);
else {
printf("%d ", i + 1);
last_r = i + 1;
}
}
// output id & ttl
printf("%05d %d", ppl[i].id, ppl[i].ttl);
// output score[]
for (int j = 1; j <= K; j++) {
if (ppl[i].score[j] >= 0)
printf(" %d", ppl[i].score[j]);
else if (ppl[i].score[j] == -1)
printf(" 0");
else
printf(" -");
}
printf("\n");
}
(2)是否参与排名?输出小分时到底是0
还是-
?
只有所有都没编译过或者根本没提交过的不参与排名。那么我们规定每个user每个题目的小分意义如下:-2:
未提交-1:
提交了但未编译通过0:
编译通过了但得分为0
初始时所有题目都为-2。
那么在读取数据时,就可以区分是否提交了。而当编译通过一道题时,就把该用户的flag
置true
,说明该用户参与排名。
for (int i = 1; i <= M; i++) {
int tmp_id, tmp_p, tmp_s;
scanf("%d %d %d", &tmp_id, &tmp_p, &tmp_s);
if (tmp_s > ppl[tmp_id - 1].score[tmp_p])
ppl[tmp_id - 1].score[tmp_p] = tmp_s;
if (tmp_s >= 0)
ppl[tmp_id - 1].flag = true;
}
而在输出小分时,若为-1
,说明是提交了,那么要显示0分;若为-2
,说明根本没提交过,输出-
// output score[]
for (int j = 1; j <= K; j++) {
if (ppl[i].score[j] >= 0)
printf(" %d", ppl[i].score[j]);
else if (ppl[i].score[j] == -1)
printf(" 0");
else
printf(" -");
}
完整代码
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<stdio.h>
#include<math.h>
#include<map>
#include<set>
#include<queue>
#include<string.h>
using namespace std;
int N, K, M;
class User {
public:
int id, ttl, pfc;
bool flag;
vector<bool> full;
vector<int> score;
};
vector<User> ppl;
void Init() {
ppl.resize(N);
for (int i = 0; i < N; i++) {
ppl[i].id = i + 1;
ppl[i].ttl = 0;
ppl[i].pfc = 0;
ppl[i].flag = false;
ppl[i].score.resize(K + 1, -2);
}
}
bool cmp(User x, User y) {
if (x.ttl != y.ttl)
return x.ttl > y.ttl;
else {
if (x.pfc != y.pfc)
return x.pfc > y.pfc;
else
return x.id < y.id;
}
}
int main() {
scanf("%d %d %d", &N, &K, &M);
vector<int> flm(K + 1);
for (int i = 1; i <= K; i++)
scanf("%d", &flm[i]);
Init();
for (int i = 1; i <= M; i++) {
int tmp_id, tmp_p, tmp_s;
scanf("%d %d %d", &tmp_id, &tmp_p, &tmp_s);
if (tmp_s > ppl[tmp_id - 1].score[tmp_p])
ppl[tmp_id - 1].score[tmp_p] = tmp_s;
if (tmp_s >= 0)
ppl[tmp_id - 1].flag = true;
}
// calculate pfc & ttl
for (int i = 0; i < ppl.size(); i++) {
for (int j = 1; j <= K; j++) {
if (ppl[i].score[j] > 0) {
ppl[i].ttl += ppl[i].score[j];
if (ppl[i].score[j] == flm[j])
ppl[i].pfc++;
}
}
}
sort(ppl.begin(), ppl.end(), cmp);
for (int i = ppl.size() - 1; i >= 0; i--) {
if (ppl[i].ttl > 0)
break;
else {
if (!ppl[i].flag)
ppl.erase(ppl.begin() + i, ppl.begin() + i + 1);
}
}
int last_r = 1;
for (int i = 0; i < ppl.size(); i++) {
// output rank
if (i == 0)
printf("1 ");
else {
if (ppl[i].ttl == ppl[i - 1].ttl)
printf("%d ", last_r);
else {
printf("%d ", i + 1);
last_r = i + 1;
}
}
// output id & ttl
printf("%05d %d", ppl[i].id, ppl[i].ttl);
// output score[]
for (int j = 1; j <= K; j++) {
if (ppl[i].score[j] >= 0)
printf(" %d", ppl[i].score[j]);
else if (ppl[i].score[j] == -1)
printf(" 0");
else
printf(" -");
}
printf("\n");
}
return 0;
}