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
题目意思原来自己一直都没懂
在给出的a[]序列中，a[i]是在所求的b[]序列中在i前面比i大的数的个数
eg：5
4 3 1 0 0
a[1]=4,即在b中，1的前面有四个数比1大，a[2]=3 ，即2的前面有3个数比2大...a[4]=0,即在4的前面有0个数比4大
则b[]：4 3 5 2 1
// time mem
// 264ms 2032kb
//by Orcz
// 2015/4/13
/*题目意思原来自己一直都没懂
在给出的a[]序列中，a[i]是在所求的b[]序列中在i前面比i大的数的个数
eg：5
4 3 1 0 0
a[1]=4,即在b中，1的前面有四个数比1大，a[2]=3 ，即2的前面有3个数比2大...a[4]=0,即在4的前面有0个数比4大
则b[]：4 3 5 2 1
*/
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int rcd[10005];
int ans[10005];
int n;
struct node{
int l,r,len;
}tree[4*10005];
void build(int v,int l,int r)
{
tree[v].l=l;
tree[v].r=r;
tree[v].len=l-r+1;
if(l==r) return;
int mid=(l+r)>>1;
build(v*2,l,mid+1);
build(v*2+1,mid,r);
}
int query(int v,int k)
{
tree[v].len--;
if(tree[v].l == tree[v].r) return tree[v].l;
if(k <= tree[2*v].len) return query(2*v,k);
else query(2*v + 1,k - tree[2*v].len);
}
void solve()
{
for(int i = 1;i <= n; ++i) cin>>rcd[i];
build(1,n,1);
int leap=0;
int pos;
for(int i = 1;i <= n; ++i){
if(tree[1].len <= rcd[i]) {leap = 1;break;}
pos = query(1,rcd[i] + 1);
ans[pos] = i;
}
if(leap) cout<<"No solution"<<endl;
else {for(int i = n;i > 1; --i) printf("%d ",ans[i]);
printf("%d
",ans[1]);}
}
int main()
{
while(~scanf("%d",&n))
solve();
}
网上看了别人的题解，是用STL的
如例子 4 3 1 0 0 我们只要从后面开始，如a[5]=0，那么5之前就有0个数比5大，所以5的位置是 a[5]+1=1 已确定：5
a[4]=0, 那么4之前就有0个数比4大，所以4的位置是 a[4]+1=1 已确定：4 5
a[3]=1, 那么3之前就有1个数比3大，所以3的位置是 a[3]+1=2 已确定：4 3 5
a[2]=3, 那么2之前就有3个数比2大，所以2的位置是 a[2]+1=4 已确定：4 3 5 2
a[1]=4, 那么1之前就有4个数比1大，所以1的位置是 a[1]+1=5 已确定：4 3 5 2 1
因为是从后面开始插入的，即是从大到小插入i值，所以是正确的
#include<cstdio>
#include<cstring>
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
int rcd[10005];
int n;
void solve()
{
vector<int> v;
for(int i = 0;i < n; ++i)
cin>>rcd[i];
v.push_back(0);
bool flag=true;
for(int i = n-1 ;i >= 0; --i){
if(v.size() <= rcd[i])
{
flag = false;
break;
}
v.insert(v.begin() + rcd[i] + 1, i + 1);
}
if(flag) {
for(int i = 1 ;i < n ; ++i)
cout<<v[i]<<" ";
cout<<v[n]<<endl;
}
else cout<<"No solution"<<endl;
}
int main()
{
while(~scanf("%d",&n))
solve();
}