1055 The World‘s Richest

题目描述
思路：本题较为经典。抽取题目模型主要就是如何在一个区间内的k个链表中求出m个最大值。简称K路归并问题。
首先将每个富豪划分到每个年龄中，然后对每个年龄里面的富豪都进行排序。则会形成N个链表，N是年龄区间长度。每个链表表头就是该年龄中最大的。
对于这个区间的最大值就是去扫描这个区间的每个链表表头看谁最大，然后取出，同时这个链表的指针下移一位。
复杂度分析：主要时间复杂度在查询中，总共K次查询，查前M个人，在某个区间内找最大值（假设不用堆维护），则为200，总共时间复杂度为200KM
另外一种解法：柳神解法
直接对富豪进行排序，顺序一定是满足财富 年龄 姓名。
然后遍历这个数组，如果是在这个年龄段的就将其纳入。
另外，由于只询问M个人不超过100，所以每个年龄段肯定不超过100，故K次询问不必遍历所有原始数组，只需要遍历每个年龄段前100个。所以需要开一个新的数组，将每个年龄段的前100放进去，用这个数组用来查询。时间复杂度优化为100200K 与第一种思路时间复杂度差不多。

#include
#include
#include
#include
using namespace std;
const int N = 1e5+10;
struct Person{
    string name;
    int age,money;
    bool operator < (const Person p) const{
        if(money != p.money)
            return money > p.money;
        if(age != p.age) return age < p.age;
        return name < p.name;
    }
};
vector<Person> ages[210];
int idx[N];
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i = 0;i < n;i++){
        char s[10];
        int money,age;
        scanf("%s%d%d",s,&age,&money);
        ages[age].push_back({s,age,money});
    }
    for(int i = 0;i <= 200;i++)
        sort(ages[i].begin(),ages[i].end());
    for(int i = 1;i <= m;i++){
        int c,min_age,max_age;
        scanf("%d%d%d",&c,&min_age,&max_age);
        memset(idx,0,sizeof idx);
        bool flag = true;
        printf("Case #%d:\n",i);
        while(c--){
            int t = -1;
            for(int j = min_age;j <= max_age;j++){
                if(idx[j] < ages[j].size()){
                    if(t == -1 || ages[j][idx[j]] < ages[t][idx[t]])
                        t = j;                    
                }
            }
            if(t == -1) break;
            flag = false;
            printf("%s %d %d\n",ages[t][idx[t]].name.c_str(),ages[t][idx[t]].age,ages[t][idx[t]].money);
            idx[t]++;                
        }
        if(flag)
            printf("None\n");
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53