首页 > 代码库 > 火柴排队
火柴排队
题目描述 Description
涵涵有两盒火柴，每盒装有 n 根火柴，每根火柴都有一个高度。现在将每盒中的火柴各自排成一列，同一列火柴的高度互不相同，两列火柴之间的距离定义为：
，其中 ai表示第一列火柴中第 i 个火柴的高度，bi表示第二列火柴中第 i 个火柴的高度。
每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离，最少需要交换多少次？如果这个数字太大，请输出这个最小交换次数对 99,999,997 取模的结果。
输入描述 Input Description
共三行，第一行包含一个整数 n，表示每盒中火柴的数目。
第二行有 n 个整数，每两个整数之间用一个空格隔开，表示第一列火柴的高度。
第三行有 n 个整数，每两个整数之间用一个空格隔开，表示第二列火柴的高度。
输出描述 Output Description
输出共一行，包含一个整数，表示最少交换次数对 99,999,997 取模的结果。
样例输入 Sample Input
[Sample 1]
4
2 3 1 4
3 2 1 4
[Sample 2]
4
1 3 4 2
1 7 2 4
样例输出 Sample Output
[Sample 1]
1
[Sample 2]
2
数据范围及提示 Data Size & Hint
【样例1说明】
最小距离是 0，最少需要交换 1 次，比如：交换第 1 列的前 2 根火柴或者交换第 2 列的前 2 根火柴。
【样例2说明】
最小距离是 10，最少需要交换 2 次，比如：交换第 1 列的中间 2 根火柴的位置，再交换第 2 列中后 2 根火柴的位置。
【数据范围】
对于 10%的数据， 1 ≤ n ≤ 10；
对于 30%的数据，1 ≤ n ≤ 100；
对于 60%的数据，1 ≤ n ≤ 1,000；
对于 100%的数据，1 ≤ n ≤ 100,000，0 ≤火柴高度≤ 2^31 - 1。
不会的同学看这组数据
4
a:1 3 5 7
b:7 5 3 1
将两组数据排序再离散变成
a:1 2 3 4
b:4 3 2 1
再搞出数组a的各个值需要移动到的位置
k[1]:=4; k[2]:=3; k[3]:=2; k[4]:=1;
然后就相当于求
4 3 2 1 变成1 2 3 4的最小移动步数
求一下逆序对就好啦归并或者树状数组都可以^ ^
var a,c,h:array[1..100000]of longint; n,i,j:longint; ans:int64;procedure sort(l,r:longint);var mid,i,j,k:longint;begin if l=r then exit; mid:=(l+r)div 2; sort(l,mid); sort(mid+1,r); i:=l; j:=mid+1; k:=l-1; repeat inc(k); if c[i]<c[j] then begin h[k]:=c[i]; inc(i); end else begin h[k]:=c[j]; inc(j); inc(ans,mid+1-i); ans:=ans mod 99999997; end; until (i>mid)or(j>r); while i<=mid do begin inc(k); h[k]:=c[i]; inc(i); end; while j<=r do begin inc(k); h[k]:=c[j]; inc(j); end; for i:=l to r do c[i]:=h[i];end;procedure qsort(l,r:longint);var i,j,mid,t:longint;begin i:=l; j:=r; mid:=c[i+random(j-i)]; repeat while c[i]<mid do inc(i); while c[j]>mid do dec(j); if i<=j then begin t:=c[i]; c[i]:=c[j]; c[j]:=t; t:=h[i]; h[i]:=h[j]; h[j]:=t; inc(i); dec(j); end; until i>j; if i<r then qsort(i,r); if j>l then qsort(l,j);end;begin randomize; read(n); for i:=1 to n do begin read(c[i]); h[i]:=i; end; qsort(1,n); for i:=1 to n do a[h[i]]:=i; for i:=1 to n do begin read(c[i]); h[i]:=i; end; qsort(1,n); for i:=1 to n do c[i]:=h[a[i]]; ans:=0; sort(1,n); writeln(ans);end.
var a,na,b,nb,c,k:array[1..100000]of longint; i,j,n:longint; ans:int64;procedure qsorta(l,r:longint);var i,j,mid,t:longint;begin i:=l; j:=r; mid:=a[i+random(j-i)]; repeat while a[i]<mid do inc(i); while a[j]>mid do dec(j); if i<=j then begin t:=a[i]; a[i]:=a[j]; a[j]:=t; t:=na[i]; na[i]:=na[j]; na[j]:=t; inc(i); dec(j); end; until i>j; if i<r then qsorta(i,r); if j>l then qsorta(l,j);end;procedure qsortb(l,r:longint);var i,j,mid,t:longint;begin i:=l; j:=r; mid:=b[i+random(j-i)]; repeat while b[i]<mid do inc(i); while b[j]>mid do dec(j); if i<=j then begin t:=b[i]; b[i]:=b[j]; b[j]:=t; t:=nb[i]; nb[i]:=nb[j]; nb[j]:=t; inc(i); dec(j); end; until i>j; if i<r then qsortb(i,r); if j>l then qsortb(l,j);end;function lowbit(x:longint):longint;begin lowbit:=x and -x;end;procedure add(k:longint);begin while k<=n do begin inc(c[k]); k:=k+lowbit(k); end;end;function getsum(k:longint):longint;begin getsum:=0; while k>0 do begin inc(getsum,c[k]); k:=k-lowbit(k); end;end;begin read(n); for i:=1 to n do begin read(a[i]); na[i]:=i; end; for i:=1 to n do begin read(b[i]); nb[i]:=i; end; qsorta(1,n); qsortb(1,n); for i:=1 to n do a[na[i]]:=i; for i:=1 to n do b[nb[i]]:=i; for i:=1 to n do k[i]:=nb[a[i]]; ans:=0; for i:=1 to n do begin add(k[i]); inc(ans,i-getsum(k[i])); ans:=ans mod 99999997; end; write(ans);end.