POJ2182总结

Lost Cows

题目来源

Description

N (2 <= N <= 8,000) cows have unique brands in the range 1..N. In a spectacular display of poor judgment, they visited the neighborhood ‘watering hole’ and drank a few too many beers before dinner. When it was time to line up for their evening meal, they did not line up in the required ascending numerical order of their brands.

Regrettably, FJ does not have a way to sort them. Furthermore, he’s not very good at observing problems. Instead of writing down each cow’s brand, he determined a rather silly statistic: For each cow in line, he knows the number of cows that precede that cow in line that do, in fact, have smaller brands than that cow.

Given this data, tell FJ the exact ordering of the cows.

Input

* Line 1: A single integer, N

* Lines 2..N: These N-1 lines describe the number of cows that precede a given cow in line and have brands smaller than that cow. Of course, no cows precede the first cow in line, so she is not listed. Line 2 of the input describes the number of preceding cows whose brands are smaller than the cow in slot #2; line 3 describes the number of preceding cows whose brands are smaller than the cow in slot #3; and so on.

Output

* Lines 1..N: Each of the N lines of output tells the brand of a cow in line. Line #1 of the output tells the brand of the first cow in line; line 2 tells the brand of the second cow; and so on.

Sample Input

5
1
2
1
0

Sample Output

2
4
5
3
1

我的代码

将每一个牛前面比自己编号小的数字的数组number[i]，按照倒序的方向，第i个牛的位置是，从1开始的第number[i]个没有被确定的数字。

例如第二个到第五个牛的数组为1、2、1、0，那么第五只牛是从1开始第0（1）个未被确定的数字，即1；第四只牛是从1开始的第1（2）个未被确定的数字，因为1已经被确定了，所以第四只牛的位置是3；以此类推。

#include<stdio.h>
#include<string.h>

int n;
int flag[8001];//标记第i头牛是否已经出现过了 
int order[8001];//记录每一个牛的编号 
int number[8001];

int main()
{
	memset(order,0,sizeof(order));
	memset(flag,0,sizeof(flag));
	scanf("%d",&n);
	for (int i=2;i<=n;i++){
		scanf("%d",&number[i]);
	}
	number[1]=0;
	for (int i=n;i>0;i--){
		for (int j=1;j<=n;j++){
			if (flag[j]==0){
				if (number[i]==0){
					order[i]=j;
					flag[j]=1;
					break;
				}else{
					number[i]--;
				}
			}
		}
	}
	for (int i=1;i<=n;i++){
		printf("%d\n",order[i]);
	}
	return 0;
}