20200322问题 E: 运动员名次

题目描述

LZY经过他的不懈努力，终于成为第2147483647届奥运会名次排序员。现在给LZY N 名运动员的成绩，找出他们的相对名次并授予前三名对应的奖牌。前三名运动员将会被分别授予 “金牌”，“银牌” 和“ 铜牌”（“Gold Medal”, “Silver Medal”, “Bronze Medal”），第四名及以后的运动员给出他们的排名。
(注：分数越高的选手，排名越靠前。)
输入
测试样例由多组测试数据组成。每组测试数据第一行输入一个正整数 n ( 1 <= n <= 10000）代表运动员的数量。
接下来一行输入n个整数 ni ( 0 <= ni <= 1000000 ） 代表运动员的成绩，所有运动员的成绩都是不相同的。
输出
按照给LZY的运动员名单，输出各个运动员的成绩
样例输入 Copy
5
1 2 3 4 5
5
5 4 3 2 1
样例输出 Copy
5 4 Bronze Medal Silver Medal Gold Medal
Gold Medal Silver Medal Bronze Medal 4 5

就这么个问题做题的时候都快把我想疯了。唉，真是感叹自己能力不足啊。

我一开始的思路是结构体排序，初始排名node，排序后node1，然后两个for找当前i(node[i])在哪个j(node1[j])里面可以找到，即node[i].sc==node[j].sc，这样就把node1[j]的排名给输出来就好，然而两个for超时了，然后用二分查找也不行，于是换了一种思路。

解题思路：我给每个数字加个位置标记pos，第一个输入pos就是0,第二个就是1，第三个2…依次下去，然后根据pos来给数字相应的排名,例如node1[node[0].pos].rnk=-1,表示5这个数字的位置是2，然后这个位置的排名是第一名(Gold Medal).这样子最后输出只要按照位置顺序输出node1[i].rnk就行了

样例测试结果：

AC代码：

#include<iostream>
#include<algorithm>
using namespace std;
struct Node{
	int sc;
	int pos;
	int rnk;
}node[10010],node1[10010];

bool cmp(Node a, Node b){
	return a.sc>b.sc;
}

int main(){
	int n;
	while(cin>>n){
		for(int i = 0; i < n; i++){
			cin>>node[i].sc;
			node[i].pos = i;
			node1[i].sc = node[i].sc;
		}
		sort(node, node+n, cmp);
		int t = 0;
		for(int i = 0; i <= n-1; i++){
			if(i==0){
				node[i].rnk = -1;
				node1[node[i].pos].rnk = node[i].rnk;
			}
			else if(i==1){
				node[i].rnk = -2;
				node1[node[i].pos].rnk = node[i].rnk;
			}
			else if(i==2){
				node[i].rnk = -3;
				node1[node[i].pos].rnk = node[i].rnk;
			}
			else {
				node[i].rnk = i+1;
				node1[node[i].pos].rnk = node[i].rnk;
			}
		}
		for(int i = 0; i < n; i++){
			if(i==n-1){
				if(node1[i].rnk==-1)cout<<"Gold Medal";
				else if(node1[i].rnk==-2)cout<<"Silver Medal";
				else if(node1[i].rnk==-3)cout<<"Bronze Medal";
				else cout<<node1[i].rnk;
			}else{
				if(node1[i].rnk==-1)cout<<"Gold Medal"<<" ";
				else if(node1[i].rnk==-2)cout<<"Silver Medal"<<" ";
				else if(node1[i].rnk==-3)cout<<"Bronze Medal"<<" ";
				else cout<<node1[i].rnk<<" ";
			}
		}
		cout<<endl;
	}
	return 0;
}

总结：这里string数组直接放数字进去，我输出来的时候是方框，搞得我很头疼，迫不得已把字符串和数字分开来表示。