[PAT-A] 1055 The World’s Richest

Java

测试点1、2超时

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

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

        List<Student> students = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            splits = br.readLine().split(" ");
            String name = splits[0];
            int age = Integer.parseInt(splits[1]);
            int num = Integer.parseInt(splits[2]);
            students.add(new Student(name, age, num));
        }

        students.sort(Comparator.comparingInt(o -> o.age));
        StringBuilder builder = new StringBuilder();
        for (int i = 1; i <= m; i++) {
            List<Student> list = new ArrayList<>();
            splits = br.readLine().split(" ");
            int rage = Integer.parseInt(splits[0]);
            int min = Integer.parseInt(splits[1]);
            int max = Integer.parseInt(splits[2]);
            builder.append(String.format("Case #%d:\n", i));
            for (Student student : students) {
                if (student.age <= max && student.age >= min) {
                    list.add(student);
                } else if (student.age > max) {
                    break;
                }
            }

            Collections.sort(list);
            int k = 0;
            while (k < list.size() && k < rage) {
                builder.append(list.get(k));
                k++;
            }
            if (list.isEmpty()) {
                builder.append("None\n");
            }
        }
        System.out.print(builder.toString().trim());
    }
}

class Student implements Comparable<Student> {
    String name;
    int age;
    int num;

    public Student(String name, int age, int num) {
        this.name = name;
        this.age = age;
        this.num = num;
    }

    @Override
    public String toString() {
        return name + " " + age + " " + num + "\n";
    }

    @Override
    public int compareTo(Student o) {
        if (this.num != o.num) {
            return o.num - this.num;
        } else if (this.age != o.age) {
            return this.age - o.age;
        } else {
            return this.name.compareTo(o.name);
        }
    }
}

C++

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

using namespace std;

const int N = 210;

int n, Q;

struct Person {
    string name;
    int age, worth;

    bool operator<(const Person &t) const {
        if (worth != t.worth) return worth > t.worth;
        else if (age != t.age) return age < t.age;
        else return name < t.name;
    }
};

vector <Person> ages[N];
int cnt[N];

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

    char name[10];
    for (int i = 0; i < n; ++i) {
        int age, worth;
        scanf("%s%d%d", name, &age, &worth);
        ages[age].push_back({name, age, worth});
    }

    for (int i = 0; i < N; ++i) sort(ages[i].begin(), ages[i].end());

    for (int idx = 1; idx <= Q; ++idx) {
        int m, amin, amax;
        scanf("%d%d%d", &m, &amin, &amax);
        printf("Case #%d:\n", idx);

        memset(cnt, 0, sizeof cnt);
        bool exists = false;

        while (m--) {
            int t = -1;
            for (int i = amin; i <= amax; ++i)
                if (cnt[i] < ages[i].size()) {
                    if (t == -1 || ages[i][cnt[i]] < ages[t][cnt[t]])
                        t = i;
                }

            if (t == -1) break;
            auto &p = ages[t][cnt[t]++];

            printf("%s %d %d\n", p.name.c_str(), p.age, p.worth);
            exists = true;
        }

        if (!exists) printf("None\n");
    }

    return 0;
};