摘要
Title: 1541. 世界首富
Tag: 优先队列、堆、多路合并
Memory Limit: 128 MB
Time Limit: 500 ms

1541. 世界首富

题意

《福布斯》杂志每年都会根据世界上最富有的人群的年度排名发布其亿万富翁名单。
现在，你需要模拟这项工作，但你只需要统计特定年龄段的富有人群。
也就是说，给定 N 个人的净资产，你必须找到在给定年龄范围内的 M 个最富有的人。
思路

多路合并用堆实现
- 先根据年龄将对象进行分类，并将其放入 $vector$ 数组，对其按照题目要求排序
- 进行多路合并
  - 初始化：先将每组年龄最top的对象取出，放入heap，并移除该对象（其实就是指针后移）
  - 操作：然后每次进行pop，对该年龄的列表的下一个元素放入heap，并移除该元素
  - 重复上一操作，直到满足要求退出

代码

优先队列的新写法：结合decltype，即推断出类型，并放入

/*
* @Author: NEFU AB-IN
* @Date: 2022-05-12 22:09:25
* @Last Modified by: NEFU AB-IN
* @Last Modified time: 2022-05-12 22:20:43
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define SZ(X) ((int)(X).size())
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(0);                                                                                                        \
    cout.tie(0);
#define DEBUG(X) cout << #X << ": " << X << endl;
typedef pair<int, int> PII;

const int N = 210;

struct sa
{
    string name;
    int age, w;
};

signed main()
{
    IOS;
    int n, k;
    cin >> n >> k;
    vector<sa> a[N];

    for (int i = 0; i < n; ++i)
    {
        string name;
        int age, w;
        cin >> name >> age >> w;
        a[age].push_back({name, age, w});
    }
    for (int i = 0; i < N; ++i)
    {
        sort(a[i].begin(), a[i].end(), [&](sa a, sa b) {
            if (a.w != b.w)
                return a.w > b.w;
            else if (a.age != b.age)
                return a.age < b.age;
            return a.name < b.name;
        });
    }
    // 堆的比较函数，正好反过来
    auto cmp = [&](sa a, sa b) {
        if (a.w != b.w)
            return a.w < b.w;
        else if (a.age != b.age)
            return a.age > b.age;
        return a.name > b.name;
    };
    // 多路合并
    for (int C = 1; C <= k; ++C)
    {
        int m, l, r;
        cin >> m >> l >> r;
        printf("Case #%lld:\n", C);

        vector<int> idx(N);
        // decltype(cmp)获得函数指针 的类型
        priority_queue<sa, vector<sa>, decltype(cmp)> q(cmp);
        // 初始化，先放入所有的路的top
        for (int i = l; i <= r; ++i)
        {
            if (SZ(a[i]) > idx[i])
                q.push(a[i][idx[i]++]);
        }
        if (!SZ(q))
        {
            printf("None\n");
            continue;
        }
        int cnt = 0;
        while (SZ(q) && cnt < m)
        {
            sa top = q.top();
            q.pop();
            printf("%s %lld %lld\n", top.name.c_str(), top.age, top.w);
            cnt++;
            if (SZ(a[top.age]) > idx[top.age])
                q.push(a[top.age][idx[top.age]++]);
        }
    }
    return 0;
}

1541. 世界首富

题意

思路

代码