【1055】The World's Richest (25 分)

World's Richest (25 分)"/>

【1055】The World's Richest (25 分)

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<algorithm>  
#include<map>
#include<vector>
#include<queue> 
using namespace std;  
//∵题意M<100，∴预处理：将每个年龄中财富前100名以内的人全部存到另一个数组中
//后面直接在这个新数组中查询(防止超时)const int maxn=100010;int Age[maxn]={0}; //某年龄的人数
struct Person{ int age,worths;  //年龄、财富值char name[10];//姓名
}ps[maxn],valid[maxn];  //所有人、在各自年龄中财富值在100名以内的人bool cmp(Person a,Person b){ if(a.worths != b.worths)  return a.worths>b.worths; //按财富值从大到小排序else if(a.age != b.age) return a.age<b.age;  //按年龄从小到大排序return strcmp(a.name,b.name) <0;  //按姓名字典序从小到大排序
}int main(){   int n,k;  //总人数、查询人数scanf("%d%d",&n,&k);for(int i=0;i<n;i++){scanf("%s%d%d",ps[i].name,&ps[i].age,&ps[i].worths); }sort(ps,ps+n,cmp);int validNum=0;  //存放到valid数组中的人数for(int i=0;i<n;i++){if(Age[ps[i].age] < 100){  //年龄ps[i].age的人数小于100人时Age[ps[i].age]++;   //年龄ps[i].age的人数加1valid[validNum++]= ps[i];//将ps[i]加入新数组中}}int m,ageL,ageR;for(int i=1;i<=k;i++){  scanf("%d%d%d",&m,&ageL,&ageR); //前M人，年龄区间[ageL,ageR]printf("Case #%d:\n",i);int printNum=0;   //已输出的人数for(int j=0;j<validNum && printNum<m;j++){if(valid[j].age >= ageL && valid[j].age <=ageR){ printf("%s %d %d\n",valid[j].name , valid[j].age , valid[j].worths );printNum++;}}if(printNum == 0){printf("None\n");}}system("pause"); return 0;   
}