PAT-A 1055. The World's Richest (25)

2019-11-06 08:36:10

字体：大中小

来源：转载

供稿：网友

题目链接在此。

题意

给定N个人的信息（姓名、年龄、财富值），然后进行K次查询，每次查询要求输出年龄在[amin,amax]之间的财富值从小到大的前M个人的信息。如果财富值相同，则按照年龄从小到大排序，年龄相同则按照名字的字典序排序。

思路及代码

思路1

首先根据年龄排序，然后根据输入的amin和amax，找到这个区间内的人，然后对这个区间内的人再按照输出的要求排序。这种思路会有两个测试点超时。

然后为了减少使用sort函数，使用一个temp结构体数组，用来保存按照年龄排序的结果，这样就可以少用sort数组去根据年龄排序，只需要在temp和richer数组赋值操作即可，这样做仍然有一个测试点超时。

思路1代码

两个测试点超时的代码：

#include<cstdio>#include<iostream>#include<algorithm>#include<cstring>using namespace std;struct INFO{ char name[9]; int age; int wealth;}richer[100001];//sort by agebool cmp_age(INFO a, INFO b){ return a.age < b.age;} //sort for final rulesbool cmp(INFO a, INFO b){ if(a.wealth != b.wealth) return a.wealth > b.wealth; else if(a.age != b.age) return a.age < b.age; else return (strcmp(a.name, b.name ) <0 );}bool cmp_test(INFO a, INFO b){ return a.wealth < b.wealth;}int main(){ int N,K,M; scanf("%d %d",&N, &K); getchar(); //吸收换行 for(int i = 0; i < N; i++){ scanf("%s %d %d",&richer[i].name, &richer[i].age, &richer[i].wealth); } //get K queries & get result int C, amin, amax; //保存K个查询的信息 for(int i = 0 ; i < K; i++){ sort(richer, richer+N, cmp_age); scanf("%d",&C); scanf("%d",&amin); scanf("%d",&amax); //find richers whose age in [amin,amax] int start; for(start = 0; start < N; start++){ if(richer[start].age >= amin){ break; } } int end; for(end = start; end < N; end++){ if(richer[end].age > amax){ break; } } sort(richer+start, richer+end, cmp); PRintf("Case #%d:/n",i+1); if(start == end){ printf("None/n"); }else{ if(C > (end-start)){ //比如数据中只有3个，而需要打印前4 的情况 C = end-start; } //print the results for(int j = start; j < start+C; j++){ printf("%s %d %d/n",richer[j].name, richer[j].age, richer[j].wealth); } } } return 0;}

一个测试点超时的代码：

#include<cstdio>#include<iostream>#include<algorithm>#include<cstring>using namespace std;struct INFO{ char name[9]; int age; int wealth;// bool flag;}richer[100001],temp[100001];//sort by agebool cmp_age(INFO a, INFO b){ return a.age < b.age;} //sort for final rulesbool cmp(INFO a, INFO b){ if(a.wealth != b.wealth) return a.wealth > b.wealth; else if(a.age != b.age) return a.age < b.age; else return (strcmp(a.name, b.name ) <0 );}bool cmp_test(INFO a, INFO b){ return a.wealth < b.wealth;}// temp to richervoid tempToRicher(int N){ for(int i = 0; i < N; i++){ richer[i] = temp[i]; }}int main(){ int N,K,M; scanf("%d %d",&N, &K); getchar(); //吸收换行 for(int i = 0; i < N; i++){ scanf("%s %d %d",&richer[i].name, &richer[i].age, &richer[i].wealth); } //sort by age sort(richer, richer+N, cmp_age); //put ordered richer to temp for(int i = 0; i < N; i++){ temp[i] = richer[i]; } //get K queries & get result int C, amin, amax; //保存K个查询的信息 for(int i = 0 ; i < K; i++){// sort(richer, richer+N, cmp_age); scanf("%d",&C); scanf("%d",&amin); scanf("%d",&amax); //find richers whose age in [amin,amax] int start; for(start = 0; start < N; start++){ if(richer[start].age >= amin){ break; } } int end; for(end = start; end < N; end++){ if(richer[end].age > amax){ break; } } sort(richer+start, richer+end, cmp); printf("Case #%d:/n",i+1); if(start == end){ printf("None/n"); }else{ if(C > (end-start)){ //比如数据中只有3个，而需要打印前4 的情况 C = end-start; } //print the results for(int j = start; j < start+C; j++){ printf("%s %d %d/n",richer[j].name, richer[j].age, richer[j].wealth); } } tempToRicher(N); } return 0;}

思路2

既然是因为查找元素过多而超时的，那么就应该减少查找元素堆的规模。这里由于M<=100，所以将每个年龄中财富在前100名的人的信息存放在一个数组中，输出的时候到这个数组中去取即可。

思路2代码

#include<cstdio>#include<iostream>#include<algorithm>#include<cstring>using namespace std;struct INFO{ char name[9]; int age; int wealth;// bool flag;}richer[100001],valid[100001]; //valid 保存每个年龄前100人的信息//sort for final rulesbool cmp(INFO a, INFO b){ if(a.wealth != b.wealth) return a.wealth > b.wealth; else if(a.age != b.age) return a.age < b.age; else return (strcmp(a.name, b.name ) <0 );}bool cmp_test(INFO a, INFO b){ return a.wealth < b.wealth;}int main(){ int N,K,M; scanf("%d %d",&N, &K); getchar(); //吸收换行 for(int i = 0; i < N; i++){ scanf("%s %d %d",&richer[i].name, &richer[i].age, &richer[i].wealth); } //sort by age sort(richer, richer+N, cmp); //将每个年龄排名前100的人的信息放到一个数组中，提高查找效率 int num[210] = {0}; //保存每个年龄的人数 int many = 0; //保存valid数组的大小 for(int i = 0; i < N; i++){ if(num[richer[i].age] < 100) { //年龄为richer[i].age的人数小于100人时 valid[many++] = richer[i]; //将richer[i]加入数组中 num[richer[i].age]++; // 年龄为richer[i].age的人数+1 } } //get K queries & get result int C, amin, amax; //保存K个查询的信息 for(int i = 0 ; i < K; i++){ scanf("%d",&C); scanf("%d",&amin); scanf("%d",&amax); printf("Case #%d:/n",i+1); int count = 0; //已经输出的人数 for(int j = 0; j < many && count<C; j++){ if(valid[j].age>=amin && valid[j].age<=amax){ printf("%s %d %d/n",valid[j].name, valid[j].age, valid[j].wealth); count++; } } if(count == 0){ printf("None/n"); } } return 0;}

上一篇：Intensity Transformations and Histogram Equalization

下一篇：位运算之判断二的正整数幂