[ACM] SCU 1555 Inversion Sequence (线段树）

?id=1555

输入5个数

1 2 0 1 0

表示1前面有1个比它大的数，2前面有2个比它大的数…..

求一个1~n的排列，比如这个就输出3 1 5 2 4

1前面有1个比它大的数，那么1肯定在第二位

2前面有2个比它大的数，那么2肯定排在第四位，有一位被1占了。

3前面有0个比它大的数，，那么3肯定在第一位

维护线段树，叶子结点的值为1，维护和。从左到右找第多少个1就可以了。

比如1前面有1个比它大的数，那么只要从左到右找到第二个1，就是1的位置，找到后，叶子结点设为0.更新。接着找。

typedef long long ll;const int maxn=10010;int ci[maxn];int ans[maxn];int n;struct ST{int l,r;int sum;}st[maxn<<2];bool ok;int tot;int pos;void pushup(int i){st[i].sum=st[i<<1].sum+st[(i<<1)|1].sum;}void build(int i,int l,int r){st[i].l=l;st[i].r=r;if(st[i].l==st[i].r){st[i].sum=1;return;}int mid=(st[i].l+st[i].r)>>1;build(i<<1,l,mid);build((i<<1)|1,mid+1,r);pushup(i);}void query(int i,int t){if(t>st[i].sum){ok=0;return;}if(st[i].l==st[i].r){pos=st[i].l;st[i].sum=0;return;}if(t<=st[i<<1].sum)query(i<<1,t);elsequery((i<<1)|1,t-st[i<<1].sum);pushup(i);}int main(){while(scanf("%d",&n)!=EOF){ok=1;build(1,1,n);tot=0;int x;for(int i=1;i<=n;i++){scanf("%d",&x);if(!ok)continue;query(1,x+1);ans[pos]=i;}if(!ok){printf("No solution\n");continue;}printf("%d",ans[1]);for(int i=2;i<=n;i++)printf(" %d",ans[i]);printf("\n");}return 0;}

类似的一个题，给出逆序数，把它还原成原数列。

?pid=2184

每组数据第一行为一个整数N（1<=N<=1000），表示该序列的数字个数。

第二行为N个整数，第i个数字表示排在ai之后比ai小的数字个数。

Output

输出为一行N个整数，表示原数列。

Sample Input

5

2 0 1 0 0

Sample Output

3 1 4 2 5

const int maxn=1110;int ans[maxn];bool vis[maxn];int n;int main(){while(scanf("%d",&n)!=EOF){memset(vis,0,sizeof(vis));int x;for(int i=1;i<=n;i++){scanf("%d",&x);int cnt=0;int pos;for(int j=1;j<=n;j++){if(cnt==x+1){vis[pos]=1;break;}if(!vis[j]){pos=j;cnt++;}}ans[i]=pos;}cout<<ans[1];for(int i=2;i<=n;i++)printf(" %d",ans[i]);printf("\n");}return 0;}

让你的心情地落到极点，一直学习生活等各个方面都做不好，最终害的还是自己。