【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;   
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/99699568