个人练习-PAT甲级-1075 PAT Judge

题目链接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。
那么在读取数据时,就可以区分是否提交了。而当编译通过一道题时,就把该用户的flagtrue,说明该用户参与排名。

    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;
}
上一篇:2.7 在Docker容器中运行Elasticsearch、Kibana和Cerebro


下一篇:judge return character