PAT A1055 The World's Richest

题目链接

解题思路

我是直接排序后进行k次查询，没有考虑是否超时，而且最后并没有超时！！

注意

参考《算法笔记》提到将每个年龄中财富值前100以内的人存储到另一个数组中(因为某个年龄中财富值在100以外的人将永远不会被输出)，后面的查询操作在新数组中进行。从而使查询不会超时。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1e5+10;
const int K=1e3+10;
int n,k;
struct People{
	char name[10];
	int age;
	int worth;
}pl[N];
struct Query{
	int m,min,max;
}qr[K];
bool cmp(const People& a,const People& b){
	if(a.worth!=b.worth) return a.worth>b.worth;
	else if(a.age!=b.age) return a.age<b.age;
	else return strcmp(a.name,b.name)<0;
}

int main(){
	scanf("%d%d",&n,&k);
	for(int i=0;i<n;i++){
		scanf("%s %d %d",&pl[i].name,&pl[i].age,&pl[i].worth);	
	}
	for(int i=0;i<k;i++){
		scanf("%d%d%d",&qr[i].m,&qr[i].min,&qr[i].max);
	}
	sort(pl,pl+n,cmp);
	for(int i=0;i<k;i++){
		printf("Case #%d:\n",i+1);
		int t=0;
		for(int j=0;j<n;j++){
			if(pl[j].age>=qr[i].min&&pl[j].age<=qr[i].max){
				t++;
				printf("%s %d %d\n",pl[j].name,pl[j].age,pl[j].worth);
			}
			if(t==qr[i].m) break;
		}
		if(t==0) printf("None\n");
	}		
	return 0;
}