[PAT-A] 1075 PAT Judge

Java

测试点4超时

import java.io.*;
import java.util.*;

public class Main {
    static final int N = 10010, M = 7;
    static int n, Q, m;
    static int[] fullScore = new int[M];
    static Map<Integer, Student> mp = new HashMap<>();
    static List<Student> v = new ArrayList<>();

    static class Student implements Comparable<Student> {
        int id;
        int[] score;
        int pNum;
        int total;
        int r;
        boolean flag;
        boolean[] isSubmitted;
        boolean[] hasP;

        public Student(int id) {
            this.id = id;
            this.score = new int[M];
            this.isSubmitted = new boolean[M];
            this.hasP = new boolean[M];
            this.flag = false;
            this.pNum = 0;
            this.total = 0;
        }

        @Override
        public int compareTo(Student t) {
            if (this.total != t.total) {
                return t.total - this.total;
            } else if (this.pNum != t.pNum) {
                return t.pNum - this.pNum;
            } else {
                return this.id - t.id;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] parts = br.readLine().split(" ");
        n = Integer.parseInt(parts[0]);
        Q = Integer.parseInt(parts[1]);
        m = Integer.parseInt(parts[2]);

        String[] fullScoreParts = br.readLine().split(" ");
        for (int i = 1; i <= Q; ++i) {
            fullScore[i] = Integer.parseInt(fullScoreParts[i - 1]);
        }

        for (int i = 0; i < m; ++i) {
            parts = br.readLine().split(" ");
            int id = Integer.parseInt(parts[0]);
            int pid = Integer.parseInt(parts[1]);
            int score = Integer.parseInt(parts[2]);

            if (!mp.containsKey(id)) {
                mp.put(id, new Student(id));
            }

            Student stu = mp.get(id);
            if (score != -1) {
                stu.score[pid] = Math.max(score, stu.score[pid]);
                stu.isSubmitted[pid] = true;
                if (!stu.hasP[pid] && score == fullScore[pid]) {
                    stu.pNum++;
                    stu.hasP[pid] = true;
                }
                stu.flag = true;
            } else {
                stu.isSubmitted[pid] = true;
                stu.score[pid] = Math.max(0, stu.score[pid]);
            }
        }

        for (Student stu : mp.values()) {
            if (stu.flag) {
                for (int i = 1; i <= Q; ++i) {
                    stu.total += stu.score[i];
                }
                v.add(stu);
            }
        }

        Collections.sort(v);

        v.get(0).r = 1;

        for (int i = 0; i < v.size(); ++i) {
            if (i > 0) {
                if (v.get(i).total == v.get(i - 1).total) v.get(i).r = v.get(i - 1).r;
                else v.get(i).r = i + 1;
            }

            System.out.printf("%d %05d %d", v.get(i).r, v.get(i).id, v.get(i).total);
            for (int j = 1; j <= Q; ++j) {
                if (!v.get(i).isSubmitted[j]) System.out.print(" -");
                else System.out.print(" " + v.get(i).score[j]);
            }
            System.out.println();
        }

        br.close();
    }
}

C++

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <vector>

using namespace std;

const int N = 10010, M = 7;

int n, Q, m;
int fullscore[M];

struct Student {
    int id, score[M], pnum, total, r;
    bool flag, is_submitted[M], has_p[M];

    bool operator<(const Student &t) const {
        if (total != t.total) return total > t.total;
        else if (pnum != t.pnum) return pnum > t.pnum;
        else return id < t.id;
    }
};

unordered_map<int, Student> mp;
vector<Student> v;

int main() {
    scanf("%d%d%d", &n, &Q, &m);
    for (int i = 1; i <= Q; ++i) scanf("%d", &fullscore[i]);
    for (int i = 0; i < m; ++i) {
        int id, pid, score;
        scanf("%d%d%d", &id, &pid, &score);

        mp[id].id = id;
        if (score != -1) {
            mp[id].score[pid] = max(score, mp[id].score[pid]);
            mp[id].is_submitted[pid] = true;
            if (!mp[id].has_p[pid] && score == fullscore[pid]) {
                mp[id].pnum++;
                mp[id].has_p[pid] = true;
            }
            mp[id].flag = true;
        } else {
            mp[id].is_submitted[pid] = true;
            mp[id].score[pid] = max(0, mp[id].score[pid]);
        }
    }

    for (auto &it: mp)
        if (it.second.flag) {
            auto &stu = it.second;
            for (int i = 1; i <= Q; ++i)
                stu.total += stu.score[i];
            v.push_back(stu);
        }

    sort(v.begin(), v.end());

    v[0].r = 1;

    for (int i = 0; i < (int) v.size(); ++i) {
        if (i > 0) {
            if (v[i].total == v[i - 1].total) v[i].r = v[i - 1].r;
            else v[i].r = i + 1;
        }

        printf("%d %05d %d", v[i].r, v[i].id, v[i].total);
        for (int j = 1; j <= Q; ++j) {
            if (!v[i].is_submitted[j]) printf(" -");
            else printf(" %d", v[i].score[j]);
        }
        printf("\n");
    }

    return 0;
}