CODEVS 3286 火柴排队

【题目描述 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。

【解题思路】

很明显可以看出，排序之后一一对应的值就是最小值

这个题刚开始我是把A排序，然后按照A的变化去变换B然后求逆序对，这个做法并不是正确的因为B刚开始也是无序的，如果将B按照A的方式求逆序对并不能得出正确的解。

应该把A,B都排一下序，然后按照B的标号处理A，就是另开一个C数组，数组变量是A的序号，组内储存对应位置B的标号，表示需要把在A[I]元素移动到j位置上，再将A重标号后的数据求逆序对。

  1 program huochai;
  2 type aa=record
  3      no,sum:Longint;
  4      end;
  5      zz=array[0..100000] of aa;
  6 const mo=99999997;
  7 var n,i,ans:longint;
  8     a,f:array[0..100000] of aa;
  9     b,c,d,e:array[0..100000] of longint;
 10 procedure sort(l,r: longint; var c:zz);
 11       var
 12          i,j,x,y: longint;
 13       begin
 14          i:=l;
 15          j:=r;
 16          x:=c[(l+r) div 2].sum;
 17 
 18          repeat
 19            while c[i].sum<x do
 20             inc(i);
 21            while x<c[j].sum do
 22             dec(j);
 23            if not(i>j) then
 24              begin
 25                 c[0]:=c[i];
 26                 c[i]:=c[j];
 27                 c[j]:=c[0];
 28                 inc(i);
 29                 j:=j-1;
 30 
 31              end;
 32 
 33          until i>j;
 34          if l<j then
 35            sort(l,j,c);
 36          if i<r then
 37            sort(i,r,c);
 38       end;
 39 
 40 procedure guibing(l,r:longint);
 41 var mid,i,q1,q2,q3:longint;
 42 begin
 43     mid:=(l+r) div 2;
 44     if l+1<r then
 45     begin
 46         guibing(l,mid);
 47         guibing(mid+1,r);
 48     end;
 49     for i:=l to mid do
 50     c[i]:=b[i];
 51     for i:=mid+1 to r do
 52     d[i]:=b[i];
 53     q1:=l;
 54     q2:=mid+1;
 55     q3:=l;
 56     while (q1<mid+1) and (q2<r+1) do
 57     begin
 58         if c[q1]<d[q2] then
 59         begin
 60             e[q3]:=c[q1];
 61             inc(q1);
 62             inc(q3);
 63         end
 64         else
 65         begin
 66             e[q3]:=d[q2];
 67             ans:=((mid-q1+1) mod mo+ans) mod mo;
 68             inc(q3);
 69             inc(q2);
 70         end;
 71     end;
 72         if q2=r+1 then
 73         for i:=q1 to mid do
 74         begin
 75             e[q3]:=c[i];
 76             inc(q3);
 77         end
 78         else
 79         for i:=q2 to r do
 80         begin
 81             e[q3]:=d[i];
 82             inc(q3);
 83         end;
 84         for i:=l to r do b[i]:=e[i];
 85 
 86 end;
 87 
 88 begin
 89     read(n);
 90     for i:=1 to n do read(a[i].sum);
 91     for i:=1 to n do
 92     begin
 93         a[i].no:=i;
 94         f[i].no:=i;
 95     end;
 96     for i:=1 to n do read(f[i].sum);
 97      sort(1,n,a);
 98      sort(1,n,f);
 99     for i:=1 to n do b[a[i].no]:=f[i].no;//重点在这里！！！
100 
101     guibing(1,n);
102     writeln(ans);
103 end.