Description
对于一个集合S={1,2,3,...N}的任一排列a1、a2、a3、... aN,我们定义ai的逆序数为∑(aj>ai | j<i),即排在ai前的所有比ai大的数的个数。我们把每个数的逆序数按下标排出就构成排列a1、a2、a3、... aN的一个逆序排列。比如排列 3 1 2的逆序排列为1 1 0(从左往右依次是1的逆序数、2的逆序数、3的逆序数)。
现在我们给出一个排列的逆序排列,请求出原排列。
Input
输入包含多组测试数据。
首先第一行输入一个数T(T<=10),表示总共有T组测试数据。
接下来是每组测试数据,第一行是一个数N(N<=100000),表示是N个数的排列。然后接下来一行是N个数字(数字之间用空格隔开<=N),表示这个排列。
Output
首先,输出Case #X:其中X代表是第X组数据(具体格式参照样例)。
然后,输出原排列(数字之间用一个空格隔开、注意行末无空格)。
Sample Input
3
2
1 0
3
1 1 0
4
3 2 1 0
Sample Output
Case #1:
2 1
Case #2:
3 1 2
Case #3:
4 3 2 1
Hint
巨大的输入输出,推荐printf,scanf
Source
humanjustic
思路:
线段树,开始一直想用线段树,却想不到好的方法,最后终于想到了。。。
代码:
#include<iostream> using namespace std; #define N 100005 struct Treenode{ int l; int r; int v; int c; }; Treenode arr[N*3]; int ans[N]; void bulid(int l,int r,int k) { arr[k].l = l; arr[k].r = r; arr[k].c = 0; if(l==r) return; int mid = (l+r)>>1; bulid(l,mid,2*k); bulid(mid+1,r,2*k+1); } void insert(int d,int v,int k) { if(arr[k].l==arr[k].r) { arr[k].v = v; arr[k].c+=1; ans[d] = v; return; } int mid = (arr[k].l+arr[k].r)>>1; if(d+arr[2*k].c>mid) insert(d+arr[2*k].c,v,2*k+1); else insert(d,v,2*k); arr[k].c = arr[2*k].c+arr[2*k+1].c; } int main() { int t,cnt = 1; scanf("%d",&t); while(t--) { int n,tmp; scanf("%d",&n); bulid(1,n,1); for(int i=1;i<=n;i++) { scanf("%d",&tmp); insert(tmp+1,i,1); } printf("Case #%d:\n",cnt++); for(int i=1;i<n;i++) printf("%d ",ans[i]); printf("%d\n",ans[n]); } }
相关推荐
BOJ的题目1023. Ancient Keyboard解法 源代码
boj 上08 09 年复试模拟题的答案
JAVA_BOJ
boj:算法
Algorithm-BOJ.zip,BekJon在线法官(Java,Kotlin,SWIFT)和PS路线图,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
BOJ
Algorithm-BOJ-PSJ.zip,Baykon在线判断JAVA问题解决方法(第二章),算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
Algorithm-BOJ-AutoCommit.zip,当您解决baekjoon online judge的问题时,它会自动提交并推送到远程存储库。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
Algorithm-boj-auto-submit.zip,日本央行cli提交脚本,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
资源分类:Python库 所属语言:Python 资源全名:boj-0.0.1.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
通过这本图画书展示您的创造力,其中包括Boj和朋友。 一本有趣的,全数字化且可重复使用的着色书,可用于 通过这本图画书展示您的创造力,其中包括Boj和朋友。 一本有趣的全数字可重复使用的图画书,专为孩子,父母...
解决问题 Boj.kr
欢迎来到PS_BOJ 이곳은... J이한BOJ문제들의AC코드들이입니다。 안내 :check_mark: C ++ Python으로풀이합니다。 :check_mark: ++ C ++풀이하며 long long 필요하거나으으으으으으으으으끔씩만끔씩만끔씩만끔씩만...
BOJ:日本央行