【问题描述】
给定1~N的某个排列，可以很容易求出每个数之前有多少个比它小的数。
但反过来，如果知道每个数之前有多少个比它小的数，能否求出原先的排列呢？
【输入数据】(sequence.in)
第一行，N(1<=N<=100)
第二行，N个数，分别表示每个数之前有多少个比它小的数。
【输出数据】(sequence.out)
一行，N个数为所求的原先排列
输入样例
4
0 1 2 1
【样例输出】
1 3 4 2
int num = 6; // N
vector<int> vecNum(num); // 1, 2, ..., N
for (int i = 0; i < num; i++){
vecNum[i] = i + 1;
}
vector<int> vecInput(num); // input
vecInput[0] = 0;
vecInput[1] = 0;
vecInput[2] = 1;
vecInput[3] = 2;
vecInput[4] = 4;
vecInput[5] = 0;
vector<int> vecOutput(num); // output
vector<int>::reverse_iterator itOutput = vecOutput.rbegin();
for (vector<int>::reverse_iterator itInput = vecInput.rbegin(); itInput != vecInput.rend(); itInput++) {
*itOutput++ = vecNum[*itInput];
vecNum.erase(vecNum.begin() + *itInput);
}
// print
for (vector<int>::iterator it = vecOutput.begin(); it != vecOutput.end(); it++) {
cout << *it << endl;
}
假设题目输入的序列A（非原序列）为a_1,a_2......a_n,表示第i个数前有a_i个数（1<=i<=n），它们对应的原序列中的数的值为b_1,b_2......b_n
————————————————————————————————————————
首先考虑特殊值，对于每个序列，一定存在一个最大值k，现在在未知序列中的第i个位置，那么他一定可以满足性质：在它前面一定存在（i-1）个比它小的数,即a_i=i-1(1<=i<=n)
然后思路就清晰了
————————————————————————————————————————————————————
我们可以先找到序列A中满足a_i=i-1(1<=i<=n),这时可能会有多个满足条件的i，那么这时序列中的最大值应选择哪个呢？
先定义这样多个位置i组成的序列为I:i_1,i_2......i_m(1<=i<=m,m为序列长度）
并且该序列有序，即i_1<i<2<......<i_m（即保持原序列中i存在的相对位置不变）
它们对应的原序列的数分别为b_i_1,b_i_2......b_i_m
//Ps:定义只是为了方便而已
那么假定b_i_j为最大值(1<=j<m)，那么因此b_i_m<b_i_j,又因为i_j在i_m前，所以b_i_m前不存在a_i_m个比b_i_m小的数，所以，可反证j=m
——————————————————————————————————————————————————————————————
选完最大值后，应该怎样选择其他值呢？
其实很简单，当选完最大值后，将最大值从A和I中删去，那么会得到新序列A和I，这时新的A序列中会有新的最大值，并且因为序列中的所有数都比最大值小（除最大值外），所以a_k（1<=k<=n)会保持不变，那么可以用一样的方法求出新序列中的最大值，以此类推，可以得到整个序列
注意删去最大值后，原来在i_m后的数可能会进入序列I，即满足最大值的性质
——————————————————————————————————
现在是实现
怎样实现，即求出序列I，其实很简单，可以参考一下平衡树的建立，具体来说，是笛卡尔树的建立（不懂可以自己去搜，很好学的）
在这样的树里（它是二叉树），在它的子树中数字比根节点小，并且左子树中的节点所对应的序列上的位置都在根前，其实我们只需要看左子树就行了，右子树只是帮助删除操作，每一次删除时就转化为删除根节点，删除后更新树，再重新删除根节点，那么就按照删除顺序就可以得到原序列。
——
删除操作只需要将根节点去掉，再将根节点的右子树插入到左子树中就行了。（学了就懂了）//Ps：这好像是废话
#include <stdio.h>
int main()
{
int n = 0;
int arr[101];
int r[101];
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
int curr = 1;
for (int i = 0; i < n; i++)
{
for (int j = n - 1; j >= 0; j--)
{
if (arr[j] == i)
r[j] = curr++;
}
}
for (int i = 0; i < n; i++)
printf("%d ", r[i]);
printf("\n");
return 0;
}