【问题描述】
给定1~N的某个排列,可以很容易求出每个数之前有多少个比它小的数。
但反过来,如果知道每个数之前有多少个比它小的数,能否求出原先的排列呢?
【输入数据】(sequence.in)
第一行,N(1<=N<=100)
第二行,N个数,分别表示每个数之前有多少个比它小的数。
【输出数据】(sequence.out)
一行,N个数为所求的原先排列
输入样例
4
0 1 2 1
【样例输出】
1 3 4 2
【问题描述】
给定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;
}