数据结构与算法题目集7-40——奥运排行榜

我的数据结构与算法题目集代码仓：https://github.com/617076674/Data-structure-and-algorithm-topic-set

原题链接：https://pintia.cn/problem-sets/15/problems/867

题目描述：

知识点：排序

思路：分别按4个规则排序4次

注意排名相同的情况，即如果某两个国家的金牌数都是10，那么其金牌排名应当相同！

时间复杂度是O(N*M)。空间复杂度是是O(N)。

C++代码：

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

struct country {
	int number;	//国家编号
	int prizes[3];	//prizes[0]代表金牌数量，prizes[1]代表奖牌数量，prizes[2]代表国民人口数量
	int rank;
};

int N, M;
//countries1按金牌排名，countries2按奖牌排名，countries3按国民人均金牌排名，countries4按人均奖牌排名
vector<country> countries1, countries2, countries3, countries4;

bool cmp1(country c1, country c2);
bool cmp2(country c1, country c2);
bool cmp3(country c1, country c2);
bool cmp4(country c1, country c2);
void generateRank(int condition);
int findRank(int condition, int number);

int main() {
	scanf("%d %d", &N, &M);
	for(int i = 0; i < N; i++) {
		country tempCountry;
		scanf("%d %d %d", &tempCountry.prizes[0], &tempCountry.prizes[1], &tempCountry.prizes[2]);
		tempCountry.number = i;
		countries1.push_back(tempCountry);
		countries2.push_back(tempCountry);
		countries3.push_back(tempCountry);
		countries4.push_back(tempCountry);
	}
	sort(countries1.begin(), countries1.end(), cmp1);
	sort(countries2.begin(), countries2.end(), cmp2);
	sort(countries3.begin(), countries3.end(), cmp3);
	sort(countries4.begin(), countries4.end(), cmp4);
	for(int i = 0; i < 4; i++){
		generateRank(i);
	}
	for(int i = 0; i < M; i++) {
		int query;
		scanf("%d", &query);
		int ranks[4];
		for(int j = 0; j < 4; j++) {
			ranks[j] = findRank(j + 1, query);
		}
		int minIndex = 0;
		for(int j = 1; j < 4; j++) {
			if(ranks[j] < ranks[minIndex]) {
				minIndex = j;
			}
		}
		printf("%d:%d", ranks[minIndex], minIndex + 1);
		if(i == M - 1) {
			printf("\n");
		} else {
			printf(" ");
		}
	}
	return 0;
}

bool cmp1(country c1, country c2) {
	return c1.prizes[0] > c2.prizes[0];
}

bool cmp2(country c1, country c2) {
	return c1.prizes[1] > c2.prizes[1];
}

bool cmp3(country c1, country c2) {
	return c1.prizes[0] * 1.0 / c1.prizes[2] > c2.prizes[0] * 1.0 / c2.prizes[2];
}

bool cmp4(country c1, country c2) {
	return c1.prizes[1] * 1.0 / c1.prizes[2] > c2.prizes[1] * 1.0 / c2.prizes[2];
}

void generateRank(int condition) {
	if(condition == 0) {
		for(int i = 0; i < countries1.size(); i++) {
			if(i > 0 && countries1[i].prizes[0] == countries1[i - 1].prizes[0]) {
				countries1[i].rank = countries1[i - 1].rank;
			} else {
				countries1[i].rank = i;
			}
		}
	} else if(condition == 1) {
		for(int i = 0; i < countries2.size(); i++) {
			if(i > 0 && countries2[i].prizes[1] == countries2[i - 1].prizes[1]) {
				countries2[i].rank = countries2[i - 1].rank;
			} else {
				countries2[i].rank = i;
			}
		}
	} else if(condition == 2) {
		for(int i = 0; i < countries3.size(); i++) {
			if(i > 0 && countries3[i].prizes[0] * 1.0 / countries3[i].prizes[2] == countries3[i - 1].prizes[0] * 1.0 / countries3[i - 1].prizes[2]) {
				countries3[i].rank = countries3[i - 1].rank;
			} else {
				countries3[i].rank = i;
			}
		}
	} else {
		for(int i = 0; i < countries4.size(); i++) {
			if(i > 0 && countries4[i].prizes[0] * 1.0 / countries4[i].prizes[2] == countries4[i - 1].prizes[0] * 1.0 / countries4[i - 1].prizes[2]) {
				countries4[i].rank = countries4[i - 1].rank;
			} else {
				countries4[i].rank = i;
			}
		}
	}
}

int findRank(int condition, int number) {
	if(condition == 1) {
		for(int i = 0; i < countries1.size(); i++) {
			if(number == countries1[i].number) {
				return countries1[i].rank + 1;
			}
		}
	} else if(condition == 2) {
		for(int i = 0; i < countries2.size(); i++) {
			if(number == countries2[i].number) {
				return countries2[i].rank + 1;
			}
		}
	} else if(condition == 3) {
		for(int i = 0; i < countries3.size(); i++) {
			if(number == countries3[i].number) {
				return countries3[i].rank + 1;
			}
		}
	} else {
		for(int i = 0; i < countries4.size(); i++) {
			if(number == countries4[i].number) {
				return countries4[i].rank + 1;
			}
		}
	}
}

C++解题报告：