/*
编码问题(95年全国分区联赛题)：设有一个数组A：array [0..N-1] of integer；
存放的元素为0～N-1(1<N<=10)之间的整数，且A[i]≠A[j]（i≠j）。例
如当N=6时，有：A=（4，3，0，5，1，2）。此时，数组A的编码定义如下：
A[0]编码为0；
A[i]编码为：在A[0]，A[1]，…，A[i-1]中比A[i]的值小的个数
          （i=1，2，…，N-1）
∴上面数组A的编码为：B=（0，0，0，3，1，2）
    要求编程解决以下问题：

给出数组A的编码后，求出A中的原数据

例：
输入：Stat=2   {表示要解决的第（2）问题}
       N=7
       B=0 1 0 0 4 5 6
输出：A=2 3 1 0 4 5 6
*/
/*
解法：先构建数组P，初始值为0，1，2，３，……，N-1。然后从B[N-1]，B[N-2]，……，B[1]，B[0]
逆向从数组P中取数求数组A。以题中例二为例，求解过程如下图：
下标值i    B0 B1 B2  B3 B4  B5 B6
p0 p1 p2  p3 p4  p5  p6    数组A
   6
    0 1  0  0  4  5  6
                ↑    0  1  2  3  4  5  6

A[6]=p[B6]=p6=6,划去p6
   5    0 1  0  0  4  5  6
             ↑        0  1  2  3  4  5

A[5]=p[B5]=p5=5,划去p5
   4
    0 1  0  0  4  5  6
          ↑          0  1  2  3  4

A[4]=p[B4]=p4=4,划去p4
   3
    0 1  0  0  4  5  6
       ↑             0  1  2  3

A[3]=p[B3]=p0=0,划去p0
   2
    0 1  0  0  4  5  6
    ↑                1  2  3

A[2]=p[B2]=p0=1,划去p0
   1
    0 1  0  0  4  5  6
 ↑                   2  3

A[1]=p[B1]=p1=3,划去p2
   0
    0 1  0  0  4  5  6
↑                     2

A[0]=p[B0]=p0=2
    从上述求解过程中，我们得到：A=（2，3，1，0，4，5，6）。
*/
#include <iostream>

using namespace std;

void decode (int code[], int A[], int n)
{
    int * const p = new int[n];

    for (int i = 0; i < n; ++i)
        p[i] = i;
    for (int i = n - 1; i >= 0; --i) {
        A[i] = p[code[i]];
        // delete p[code[i]] from list
        for (int j = code[i]; j < i; ++j)
            p[j] = p[j + 1];
    }

    delete []p;
}

int main ()
{
    const int N = 7;
    int code[N] = {0,1,0,0,4,5,6};
    int A[N];

    decode (code, A, N);
    for (int i = 0; i < N; ++i)
        cout << A[i] << ' ';
    cout << endl;
    system ("pause");
    return 0;
}