算法1

C++ 代码

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

using namespace std;
const int MAX_N = 100010;
const int MAX_AGE = 210;
const int MAX_C = 9;

struct People {
    string name;
    int age, worth;
    bool operator<(const People& t) {
        if (worth != t.worth) return worth > t.worth;
        else if (age != t.age) return age < t.age;
        return name < t.name;
    }
}p[MAX_N], valid[MAX_N];

int agesNum[MAX_AGE];

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++) {
        char name[MAX_C];
        int age, worth;
        scanf("%s%d%d", name, &age, &worth);
        p[i] = { name, age, worth };
    }
    sort(p, p + n);

    //优化最坏情况的枚举次数，每个年龄最多记录100个人
    //最多枚举次数 200岁*100人 = 2*10^4 (10^5 减少了一个数量级)
    int idx = 0;
    for(int i = 0; i < n; i++){
        if(agesNum[p[i].age] < 100) {
            valid[idx++] = p[i];
            agesNum[p[i].age]++;
        }
    }
    n = idx;

    for (int i = 1; i <= k; i++) {
        int m, l, r;
        scanf("%d%d%d", &m, &l, &r);
        printf("Case #%d:\n", i);
        int cnt = 0;
        for (int j = 0; j < n && cnt < m; j++) {
            if (valid[j].age >= l && valid[j].age <= r) {
                printf("%s %d %d\n", valid[j].name.c_str(), valid[j].age, valid[j].worth);
                cnt++;
            }
        }
        if (cnt == 0) puts("None");
    }
    return 0;
}