reverse order 2
Time Limit: 1 Sec Memory Limit: 128 MB
Submissions: 157 Solved: 64
Description
Here is a sequence a1..n, which is a disordered sequence from 1 to N. if i < j and ai > aj, <i, j> is called a pair of inversion. And b1..n-1 is defined as follows, bk is the number of the total inversion pairs in array a, when i<=k<j. Now the array a is required while the array b is known.
Input
Several cases end with the end of the file;
And each of the cases includes two lines, a integer n(2<=n<=10^5)in the first line, and the second line followed with n-1 integer, which is in the presentation of array b;
Output
Output the answer of each case in a line, namely the array a, and a space is required between adjacent integers.
Sample Input
5
2 1 2 0
Sample Output
3 1 4 2 5
a[ 1 ] = b[ 1 ] + 1;
求 b[ i ] 時，a[ i ] 左邊比它大的有 X 個，a[ i ] 右邊比它小的有 Y 個，
則比 a[ i ] 小的一共有 ( Y - X + i - 1 ) 個，所以 a[ i ] = Y - X + i，
即 a[ i ] = b[ i ] - b[ i - 1 ] + i。
用 int 的 b 會錯誤，要 long long 的 b 。
1
/**//*
2
// int b, WA
3#include <stdio.h>
4#include <string.h>
5
6#define L 100009
7
8int has[ L ];
9
10int main() {
11 int n, i, a, b, bk;
12 while ( scanf( "%d", &n ) == 1 ) {
13 memset( has, 0, sizeof(has) );
14 bk = 0;
15 for ( i = 1; i < n; ++i ) {
16 scanf( "%d", &b );
17 a = b - bk + i;
18 bk = b;
19 has[ a ] = 1;
20 printf( "%d ", a );
21 }
22 for ( i = 1; i <= n; ++i ) {
23 if( has[ i ] == 0 ) {
24 a = i;
25 }
26 }
27 printf( "%d\n", a );
28 }
29 return 0;
30}
31
*/
32
33
34// long long b, AC
35#include <stdio.h>
36#include <string.h>
37
38#define L 100009
39
40int has[ L ];
41
42int main() 
{
43 int n, i, a;
44 long long bk, b;
45
while ( scanf( "%d", &n ) == 1 ) {
46 memset( has, 0, sizeof(has) );
47 bk = 0;
48 for ( i = 1; i < n; ++i ) {
49 scanf( "%lld", &b );
50 a = b - bk + i;
51 bk = b;
52 has[ a ] = 1;
53 printf( "%d ", a );
54
}
55 for ( i = 1; i <= n; ++i ) {
56 if( has[ i ] == 0 ) {
57 a = i;
58 }
59 }
60 printf( "%d\n", a );
61 }
62 return 0;
63}
64