北航的这道考研上机真题大意是:给定一个序列,输出该序列的各个元素在排序后的序号。
首先排序肯定是需要的, 但排序后虽然能都得到各个元素的大小标号,但原来的顺序也就不知道了。恢复序列的办法便是添加一个域,指示排序前的序号,排完序后再按排序前的序号排回来便可。
题目url:http://ac.jobdu.com/problem.php?id=1167
我的AC代码,和大家分享一下。
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int Max = 10000 + 10;
struct node
{
int d;
int sorted;
int ori;
};
node a[Max];
bool com1(node a, node b)
{
return a.d < b.d;
}
bool com2(node a, node b)
{
return a.ori < b.ori;
}
int main()
{
int n;
while(scanf("%d", &n) != EOF)
{
for(int i=0; i<n; i++)
{
scanf("%d", &a[i].d);
a[i].ori = i;
}
sort(a, a+n, com1);
int seq = a[0].sorted = 1, flag = a[0].d;
for(int i=1; i<n; i++)
if(a[i].d == flag) a[i].sorted = seq;
else
{
a[i].sorted = ++seq;
flag = a[i].d;
}
sort(a, a+n, com2);
for(int i=0; i<n; i++)
if(i != n-1) printf("%d ", a[i].sorted);
else printf("%d\n", a[i].sorted);
}
system("pause");
return 0;
}