PAT-A 1055. The World's Richest

对输入数据中不合条件的数据进行预处理，减少运行时间。

PAT(Advanced) PAT-A 1055. The World’s Richest

题目大意

给出N个人的姓名，年龄以及其拥有的财富值，进行K次查询，每次输出年龄范围[Amin,Amax]内财富排名前M个人的信息。排序优先级为财富大，年龄小，姓名字典序小。

思路

将输入的所有人按给出的规则进行排序，然后查找输出年龄范围[Amin,Amax]内的前M个人。

注意点

注意到M的取值范围是M<=100，所以必须将输入数据某个年龄中排名100以外的人去除，否则测试点2会超时。我一开始以为是查找年龄段时发生超时，尝试了二分查找最后打表记录每个年龄的数组下标，依旧会在测试点2超时。所以必须去除上面的数据。

AC代码

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdlib>
#include <stdio.h>
#include <algorithm>
// #include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <map>
#include <stack>

using namespace std;

struct People {
	char name[9];
	int age;
	int worth;
}p[100010];

bool cmp_age(People a, People b) {
	if (a.age != b.age) {
		return a.age < b.age;
	}
	else {
		return  a.worth > b.worth;
	}
}

bool cmp(People a, 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;
	}
}

struct Age {
	int head = -1;
	int end = -1;
} age_list[202];

int main() {
	int n, k;
	scanf("%d %d", &n, &k);
	for (int i = 0; i < n; i++) {
		scanf("%s %d %d", p[i].name, &p[i].age, &p[i].worth);
	}
	sort(p, p + n, cmp_age);
	int age_temp = p[0].age, count = 1;
	for (int i = 1; i < n; i++) {
		if (p[i].age == age_temp) {
			count++;
			if (count > 101) {
				p[i].age == 300;
			}
		}
		else {
			count = 0;
			age_temp = p[i].age;
		}
	}

	sort(p, p + n, cmp_age);
	for (int i = 0; i < n; i++) {
		if (p[i].age > 200) {
			n = i;
			break;
		}
	}
	sort(p , p + n, cmp);
	
	for (int i = 0; i < k; i++) {
		int m, amin, amax;
		bool flag = 0;
		scanf("%d %d %d", &m, &amin, &amax);
		printf("Case #%d:\n", i + 1);
		
		int pcount = 0;
		for (int i = 0; i < n&&pcount < m; i++) {
			if (p[i].age >= amin && p[i].age <= amax) {
				printf("%s %d %d\n", p[i].name, p[i].age, p[i].worth);
				pcount++;
			}
		}
		if (pcount == 0) {
			printf("None\n");
		}
	}

	system("pause");
	return 0;
}