[PAT-A] 1153 Decode Registration Card of PAT

Java

测试点2、3、4超时

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

public class Main {
    static class Student {
        String cardNum;
        int score;
        char level;
        int site;
        String date;
        int testeeNum;

        Student(String cardNum, int score) {
            this.cardNum = cardNum;
            this.score = score;
            this.level = cardNum.charAt(0);
            this.site = Integer.parseInt(cardNum.substring(1, 4));
            this.date = cardNum.substring(4, 10);
            this.testeeNum = Integer.parseInt(cardNum.substring(10));
        }
    }

    static class Site implements Comparable<Site> {
        int site;
        int count;

        Site(int site, int count) {
            this.site = site;
            this.count = count;
        }

        @Override
        public int compareTo(Site other) {
            if (this.count != other.count) {
                return other.count - this.count;
            } else {
                return this.site - other.site;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");
        int N = Integer.parseInt(inputs[0]);
        int M = Integer.parseInt(inputs[1]);

//        List<Student> students = new ArrayList<>();
        Map<Integer, List<Student>> sitesMap = new HashMap<>();
        Map<Character, List<Student>> levelsMap = new HashMap<>();
        Map<String, Map<Integer, Integer>> dateMap = new HashMap<>();

        for (int i = 0; i < N; i++) {
            inputs = br.readLine().split(" ");
            Student student = new Student(inputs[0], Integer.parseInt(inputs[1]));
//            students.add(student);

            sitesMap.computeIfAbsent(student.site, k -> new ArrayList<>()).add(student);

            levelsMap.computeIfAbsent(student.level, k -> new ArrayList<>()).add(student);

            dateMap.computeIfAbsent(student.date, k -> new HashMap<>())
                    .merge(student.site, 1, Integer::sum);
        }

        for (int q = 1; q <= M; q++) {
            inputs = br.readLine().split(" ");
            int type = Integer.parseInt(inputs[0]);
            String term = inputs[1];

            System.out.printf("Case %d: %d %s\n", q, type, term);

            switch (type) {
                case 1: // Query by level
                    List<Student> levelStudents = levelsMap.getOrDefault(term.charAt(0), new ArrayList<>());
                    if (levelStudents.isEmpty()) {
                        System.out.println("NA");
                    } else {
                        levelStudents.sort((a, b) -> {
                            if (a.score != b.score) {
                                return b.score - a.score;
                            } else {
                                return a.cardNum.compareTo(b.cardNum);
                            }
                        });
                        for (Student s : levelStudents) {
                            System.out.printf("%s %d\n", s.cardNum, s.score);
                        }
                    }
                    break;

                case 2: // Query by site
                    int siteNum = Integer.parseInt(term);
                    List<Student> siteStudents = sitesMap.getOrDefault(siteNum, new ArrayList<>());
                    if (siteStudents.isEmpty()) {
                        System.out.println("NA");
                    } else {
                        int total = siteStudents.stream().mapToInt(s -> s.score).sum();
                        System.out.printf("%d %d\n", siteStudents.size(), total);
                    }
                    break;

                case 3: // Query by date
                    Map<Integer, Integer> siteCounts = dateMap.getOrDefault(term, new HashMap<>());
                    if (siteCounts.isEmpty()) {
                        System.out.println("NA");
                    } else {
                        List<Site> counts = new ArrayList<>();
                        for (Map.Entry<Integer, Integer> entry : siteCounts.entrySet()) {
                            counts.add(new Site(entry.getKey(), entry.getValue()));
                        }
                        Collections.sort(counts);
                        for (Site sc : counts) {
                            System.out.printf("%d %d\n", sc.site, sc.count);
                        }
                    }
                    break;
            }
        }
    }
}

C++

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

using namespace std;

const int N = 10010, M = 1010;

int n, m;
struct Person {
    string card;
    int site;
    string date;
    int num;
    int score;
} p[N];
struct Site {
    int num;
    int total;
};
vector<Person> levels[3];    // ppl of level (0 = T  1 = A  2 = B)
vector<Person> sites[M];    // ppl in site

int main() {
    scanf("%d%d", &n, &m);

    string card, date;
    for (int i = 0; i < n; ++i) {
        int score, site, num;
        cin >> card;
        scanf("%d", &score);

        site = stoi(card.substr(1, 3));
        date = card.substr(4, 6);
        num = stoi(card.substr(10, 3));

        Person ppl = {card, site, date, num, score};
        p[i] = ppl;
        sites[site].push_back(ppl);
        if (card[0] == 'T') levels[0].push_back(ppl);
        else if (card[0] == 'A') levels[1].push_back(ppl);
        else levels[2].push_back(ppl);
    }

    for (int Q = 1; Q <= m; ++Q) {
        int type;
        scanf("%d", &type);

        if (type == 1) {
            char lchar;
            cin >> lchar;
            int lnum;
            if (lchar == 'T') lnum = 0;
            else if (lchar == 'A') lnum = 1;
            else lnum = 2;

            sort(levels[lnum].begin(), levels[lnum].end(), [](Person &a, Person &b) {
                if (a.score != b.score) return a.score > b.score;
                return a.card < b.card;
            });

            printf("Case %d: 1 %c\n", Q, lchar);
            if (levels[lnum].empty()) printf("NA\n");
            else {
                for (auto it: levels[lnum])
                    printf("%s %d\n", it.card.c_str(), it.score);
            }
        } else if (type == 2) {
            int site;
            scanf("%d", &site);

            int sum = 0;
            for (auto it: sites[site])
                sum += it.score;

            printf("Case %d: 2 %d\n", Q, site);
            if (sites[site].empty()) printf("NA\n");
            else printf("%d %d\n", sites[site].size(), sum);
        } else {
            string date;
            cin >> date;

            vector <Site> v;
            for (int i = 101; i < M; ++i) {
                int cnt = 0;
                for (auto it: sites[i])
                    if (it.date == date) cnt++;

                if (cnt > 0) v.push_back({i, cnt});
            }

            sort(v.begin(), v.end(), [](Site &a, Site &b) {
                if (a.total != b.total) return a.total > b.total;
                return a.num < b.num;
            });

            printf("Case %d: 3 %s\n", Q, date.c_str());
            if (v.empty()) printf("NA\n");
            else {
                for (auto it: v)
                    printf("%d %d\n", it.num, it.total);
            }
        }
    }

    return 0;
}