题目大意:给出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
;
}
}
}