Time Limit:2000MS Memory Limit:262144KB 64bit IO Format:%lld & %llu
Description
For sequence i1, i2, i3, … , iN, we set aj to be the number of members in the sequence which are prior to j and greater to j at the same time. The sequence a1, a2, a3, … , aN is referred to as the inversion sequence of the original sequence (i1, i2, i3, … , iN). For example, sequence 1, 2, 0, 1, 0 is the inversion sequence of sequence 3, 1, 5, 2, 4. Your task is to find a full permutation of 1~N that is an original sequence of a given inversion sequence. If there is no permutation meets the conditions please output “No solution”.
Input
There are several test cases.
Each test case contains 1 positive integers N in the first line.(1 ≤ N ≤ 10000).
Followed in the next line is an inversion sequence a1, a2, a3, … , aN (0 ≤ aj < N)
The input will finish with the end of file.
Output
For each case, please output the permutation of 1~N in one line. If there is no permutation meets the conditions, please output “No solution”.
Sample Input
5
1 2 0 1 0
3
0 0 0
2
1 1
Sample Output
3 1 5 2 4
1 2 3
No solution 这题有两种做法，一开始直接用STL里的vector A掉了这个题目，然后基神让我试下用线段树来解这个题目，我就两种方法都写了 先来线段树： 从小到大插入到第k个格子。
/*/
线段树做法：
首先，弄个长度为n的线段树，维护sum，初始值为1
那么，sum[1]等于n，代表着空着的位置的数量
现在要把某个数字插入到p位置，就在线段树找到一个位置x，使得[x]里面的sum等于p；
然后把那个1修改为0，就表示那个位置不是空着的了。 /*/
#include"iostream"
#include"cstdio"
#include"cstring"
#include"algorithm"
#include"cmath"
using namespace std;
#define MX 11111
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
int sum[MX<<2]; void PushUp(int rt) {
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
} void Build(int l,int r,int rt) {
sum[rt]=1;
if(r==l)return ;
int m=(r+l)>>1;
Build(lson);
Build(rson);
PushUp(rt);
} int Query(int p,int l,int r,int rt) {
if(l==r) { //找到点，插入，返回点的位置值
sum[rt]--;
return l;
}
int m=(l+r)>>1,ret=0;
if(p<=sum[rt<<1]) ret=Query(p,lson);//点在左边，直接向左找
else ret=Query(p-sum[rt<<1],rson);// 减去左边没去找的点
PushUp(rt);
return ret;
}
int a[MX];
int ans[MX];
int main() {
int n;
while(~scanf("%d",&n)) {
Build(1,n,1);
for(int i=1; i<=n; i++) {
scanf("%d",&a[i]);
}
bool check=1;
for(int i=1; i<=n; i++) {
if(sum[1]<a[i]+1) {
check=0;
break;
} else {
int p= Query(a[i]+1,1,n,1);
ans[p]=i;
}
}
if(!check)printf("No solution\n");
else {
int first=1;
for(int i=1; i<=n; i++) {
if(first)first=0;
else printf(" ");
printf("%d",ans[i]);
}
printf("\n");
}
}
return 0;
}
然后是STL： 从大到小插入到第k个格子。
/*/
STL-vector:
从最大的数开始插入队列；
利用vector中的insert()函数去将数字插入相应的位置；
这种方法暴力，简单。。。
但是每一次插入复杂度是O(n);
数据有点放水，还是A了。
/*/
#include"iostream"
#include"cstdio"
#include"cstring"
#include"string"
#include"algorithm"
#include"vector" using namespace std;
#define MX 10050
int num[MX]; int main() {
int n;
while(~scanf("%d",&n)) {
for(int i=0; i<n; i++) {
scanf("%d",&num[i]);
}
int flag=1;
vector<int > v;
v.push_back(0);
for(int i=n-1;i>=0; i--) {
if(v.size()<=num[i]) {
printf("No solution\n");
flag=0;
break;
}
v.insert(v.begin()+num[i],i+1);
}
if(flag) {
int first=1;
vector<int>::iterator it;
for(it=v.begin(); it!=v.end()-1; it++) {
if(first) {
first=0;
printf("%d",(*it));
}
else printf(" %d",(*it));
}
printf("\n");
}
}
return 0;
}