repeat bre sig roc rep idt 恢复 逆序
一开始看也想不到这居然要用到逆序对,归并排序。
先来看看题目:
涵涵有两盒火柴,每盒装有 n 根火柴,每根火柴都有一个高度。 现在将每盒中的火柴各自排成一列, 同一列火柴的高度互不相同, 两列火柴之间的距离定义为: ∑(ai-bi)^2
其中 ai 表示第一列火柴中第 i 个火柴的高度,bi 表示第二列火柴中第 i 个火柴的高度。
每列火柴中相邻两根火柴的位置都可以交换,请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离,最少需要交换多少次?如果这个数字太大,请输出这个最小交换次数对 99,999,997 取模的结果。
样例输入:
- 4
- 1 3 4 2
- 1 7 2 4
样例输出:
- 2
根据样例,设第二行的数为 a{1,3,4,2},第三行的数为 b{1,7,2,4}。对于题目要求通过交换使得两列火柴之间的的距离最小,满足这个要求只能使 a 中高度最小的火柴和 b 中高度最小的火柴搭配,第二小的和第二小的搭配。为了方便处理和后续的操作,把 a 和 b 进行离散化。离散化后,a{1,3,4,2},b{1,4,2,3}(离散化详解在 * 1)。遍历数组 a,查找 a[i] 在数组 b 中所对应的位置(详细处理在 * 2)(需要用二分查找 * 3),存入新数组 R,处理后为 R{1,4,2,3},R[i] 即为 a[i] 将要移到的位置,最小交换的次数正是 R 的逆序对数量。a 中的 3 要移到 R 中 3 的位置,需要向右交换两次。相同的,可以这样认为,R 中的 3 要向左移到 a 中的 3 的位置,则需要两次交换。R 中 3(即 R[4])的逆序对数量为 2,整个 R 的逆序对数量也为 2。所求最少交换次数就是 R 的逆序对数量。使用归并排序。
时间复杂度 (大概):O(7*(n log n)) 离散化:4*(n log n) ( 4 次快排)预处理二分查找 + 二分查找:2*(n log n) 归并排序:(n log n) 绝对不会超时 qwq
*1:离散化前:a{1,3,4,2},b{1,7,2,4},给每个数组的每一个数标上序号,按照数组内容带上序号一起排序,重新编号,再根据之前标上的序号排回来恢复原状。
原始状态:
a | 1 | 3 | 4 | 2 |
序号 | 1 | 2 | 3 | 4 |
b | 1 | 7 | 2 | 4 |
序号 | 1 | 2 | 3 | 4 |
按照数组内容排序:
a | 1 | 2 | 3 | 4 |
序号 | 1 | 4 | 2 | 3 |
b | 1 | 2 | 4 | 7 |
序号 | 1 | 3 | 4 | 2 |
重新编号:
a | 1 | 2 | 3 | 4 |
序号 | 1 | 4 | 2 | 3 |
b | 1 | 2 | 3 | 4 |
序号 | 1 | 3 | 4 | 2 |
按照序号重新排序恢复:
a | 1 | 3 | 4 | 2 |
序号 | 1 | 2 | 3 | 4 |
b | 1 | 4 | 2 | 3 |
序号 | 1 | 2 | 3 | 4 |
完成,a 离散化后和原来一样是因为样例特殊,参考 b 的离散化过程就好了。
*2:a[i] 在数组 b 中所对应的位置。首先列出数组。
a | 1 | 3 | 4 | 2 |
b | 1 | 4 | 2 | 3 |
序号 | 1 | 2 | 3 | 4 |
R |
i=1 的情况:a[i] 为 1,b 中的 1 在 b[1] 中,b[1] 对应的序号为 1,所以 R[i] 为 1,i=1,所以 R[1] 填上 1。
i=2 的情况:a[i]=3,b[4]=3,所以 b 中的 3 在 b[4],对应序号为 4。R[2] 填上 4
i=3:a[i]=4,b[2]=4,所以 R[i]=2,R[3] 填上 2
i=4:a[i]=2,b[3]=2,所以 R[4]=3
最终得 R 为:
R | 1 | 4 | 2 | 3 |
*3:如果查找 a[i] 在数组 b 中所对应的位置使用两重循环,则查找的时间复杂度为 O(n^2),数据范围为 n<=100000,光是查找就会超时,所以需要用二分排序。
贴上代码详细参考:
- type
- arr=array[0..100000] of longint;
- var
- a1,b1,a,r:arr;
- n,i,j:longint;
- left,right,mid:longint;
- ans:qword;
- procedure qsort(var a,b:arr); //快排a数组,捆绑b数组
- procedure sort(l,r: longint);
- var
- i,j,x,y: longint;
- begin
- i:=l;
- j:=r;
- x:=a[(l+r) div 2];
- repeat
- while a[i]<x do
- inc(i);
- while x<a[j] do
- dec(j);
- if not(i>j) then
- begin
- y:=a[i];
- a[i]:=a[j];
- a[j]:=y;
- y:=b[i];
- b[i]:=b[j];
- b[j]:=y;
- inc(i);
- dec(j);
- end;
- until i>j;
- if l<j then
- sort(l,j);
- if i<r then
- sort(i,r);
- end;
- begin
- sort(1,n);
- end;
- procedure mergesort(s,t:longint); //归并排序用来统计逆序对
- var
- mid,i,j,k:longint;
- begin
- if s=t then exit;
- mid:=(s+t) div 2;
- mergesort(s,mid);
- mergesort(mid+1,t);
- i:=s;
- j:=mid+1;
- k:=s;
- while (i<=mid) and (j<=t) do
- if a[i]<=a[j] then
- begin
- r[k]:=a[i];
- inc(i);
- inc(k);
- end
- else
- begin
- r[k]:=a[j];
- inc(j);
- inc(k);
- ans:=ans+(mid-i+1); //逆序对
- end;
- while i<=mid do
- begin
- r[k]:=a[i];
- inc(i);
- inc(k);
- end;
- while j<=t do
- begin
- r[k]:=a[j];
- inc(j);
- inc(k);
- end;
- for i:=s to t do
- a[i]:=r[i];
- end;
- begin
- assign(input,'match.in');
- assign(output,'match.out');
- reset(input);
- rewrite(output);
- readln(n);
- for i:=1 to n do
- begin
- read(a1[i]); //读入a数组
- r[i]:=i; //编号
- end;
- qsort(a1,r); //按照数组内容排序
- for i:=1 to n do a1[i]:=i; //重新编号 {离散化}
- qsort(r,a1); //按照编号排序复原
- readln;
- for i:=1 to n do
- begin
- read(b1[i]); //读入b数组
- r[i]:=i; //编号
- end;
- qsort(b1,r); //按照数组内容排序
- for i:=1 to n do b1[i]:=i; //重新编号 {离散化}
- qsort(r,b1); //按照编号排序复原
- {for i:=1 to n do //处理a[i]在数组b中所对应的位置,使用两重循环,n到达1000时就会超时,所以舍弃
- for j:=1 to n do
- if b1[i]=a1[j] then
- begin
- a[i]:=j;
- break;
- end; }
- for i:=1 to n do r[i]:=i;
- qsort(a1,r); //按照内容排序
- for i:=1 to n do //遍历每个b[i]查找在a中的位置(这里a和b交换了,所以是查找b[i]在a中的位置)
- begin
- left:=1;
- right:=n;
- mid:=(left+right) div 2;
- while (a1[mid]<>b1[i]) and (left<=right) do //二分查找,时间复杂度O(n log n)
- begin
- if a1[mid]>b1[i] then right:=mid-1
- else left:=mid+1;
- mid:=(left+right) div 2;
- end;
- a[i]:=r[mid]; //此处的a数组即为上面所讲的R数组
- end;
- ans:=0;
- fillchar(r,sizeof(r),0);
- mergesort(1,n); //归并排序统计逆序对
- writeln(ans mod 99999997); //依照题意对99999997取模
- close(input);
- close(output);
- end.
NOIP2013 提高组 T2 火柴排队
来源: http://www.bubuko.com/infodetail-2273668.html