首页 > ACM题库 > HDU-杭电 > hdu 2404 Permutation Recovery-模拟[解题报告]C++
2014
01-26

hdu 2404 Permutation Recovery-模拟[解题报告]C++

Permutation Recovery

问题描述 :

Professor Permula gave a number of permutations of the n integers 1, 2, …, n to her students. For each integer i (1 <= i <= n), she asks the students to write down the number of integers greater than i that appears before i in the given permutation. This number is denoted ai. For example, if n = 8 and the permutation is 2,7,3,5,4,1,8,6, then a1 = 5 because there are 5 numbers (2, 7, 3, 5, 4) greater than 1 appearing before it. Similarly, a4 = 2 because there are 2 numbers (7, 5) greater than 4 appearing before it.

John, one of the students in the class, is studying for the final exams now. He found out that he has lost the assignment questions. He only has the answers (the ai’s) but not the original permutation. Can you help him determine the original permutation, so he can review how to obtain the answers?

输入:

The input consists of a number of test cases. Each test case starts with a line containing the integer n (n <= 500). The next n lines give the values of a1, …, an. The input ends with n = 0.

输出:

The input consists of a number of test cases. Each test case starts with a line containing the integer n (n <= 500). The next n lines give the values of a1, …, an. The input ends with n = 0.

样例输入:

8
5
0
1
2
1
2
0
0
10
9
8
7
6
5
4
3
2
1
0
0

样例输出:

2,7,3,5,4,1,8,6
10,9,8,7,6,5,4,3,2,1


初始化均为-1,从小到大填入表格,这样每当填进去的时候,某个数前有多少个-1就有多少个数比它大,然后处理下-1之后连续的已经填好的数,就可以得到当前要填的位置了。

#include <iostream>
using namespace std;

intmain()
{
//freopen( “C:\\in.txt”, “r”, stdin);
int n;
int i, j;
int temp;
int order[501];
while( scanf(“%d”, &n) != EOF) {
if( n==0)break;
memset(order, -1,sizeof(order));

for( i=1; i<= n; ++i) {
j=0;
scanf(“%d”, &temp);
while( temp!= -1) {
if( order[j] == -1) {
temp–;
}
j++;
}
while( order[j] != -1) j++;
order[j] = i;
}

printf(“%d”, order[1] );
for( i=2; i<= n; ++i) {
printf(“,%d”,order[i] );
}
printf(“\n”);
}
return0;
}


  1. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept