A1055 The World‘s Richest [排序]

    技术2022-07-13  70

    题目大意:给出n个人的姓名、年龄和拥有的钱,然后进行k次查询,每次查询输出在年龄区间内的财富值的从大到小的前m个人的信息。如果财富值相同就就先输出年龄小的,如果年龄相同就把名字按照字典序排序输出~ 注意事项:

    题目本身不难,就是第二个点,他给你很多数据,然后你如果直接查询会消耗大量时间,然后因为依据年龄查询,每一个年龄是一个最小单位,每次查询最多输出100个用户数据,就把每个年龄财富最多的前100个人存入一个新数组,不一定会存满,然后最后再新数组上操作,这样就不会超时了,PAT就是老是卡某个点,感觉A组题所有测试点一次通过还是不容易的。加油~
    #include<iostream> #include<algorithm> #include<cstring> using namespace std; struct person { char name[15]; int age; int money; }per[100001],temp[100001]; int agecount[100001] = { 0 }; //某年龄的人数 bool cmp(person a, person b) { if (a.money != b.money) return a.money > b.money; else if (a.age != b.age) return a.age < b.age; else return strcmp(a.name, b.name) < 0; } int main() { int n, m; cin >> n >> m; for (int i = 0; i < n; i++) { cin >> per[i].name >> per[i].age >> per[i].money; } sort(per, per + n, cmp); int num = 0; for (int i = 0; i < n; i++) { if (agecount[per[i].age] < 100) { agecount[per[i].age]++; temp[num++] = per[i]; } } int c, age1, age2; for (int i = 0; i < m; i++) { cin >> c >> age1 >> age2; cout << "Case #"<<i+1<<":"<<endl; int count = 0; for (int j = 0; j < num; j++) { if (temp[j].age <= age2 && temp[j].age >= age1) { cout << temp[j].name <<" "<< temp[j].age <<" "<< temp[j].money << endl; count++; if (count == c) break; } } if (count == 0) { cout << "None" << endl; } } }
    Processed: 0.009, SQL: 9