【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的人数加1
      valid[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;   
}