OJ1-3灯塔归并排序

思路

建模

这道题相当于把灯塔先按照x坐标排序之后再求y坐标的顺序对数，比如坐标分别为(1,1),(2,3),(3,2),(4,4)的四座灯塔，则先按x坐标排序之后变为(1,1),(2,3),(3,2),(4,4)，再求数列1 3 2 4的顺序对数即可。

这里顺序对有(1,3),(1,2),(1,4),(3,4),(2,4)，所以互相能够照明的灯塔数为5

求顺序对数的两种方法

1.暴力数数

复杂度\(\Theta(n^2)\)

在此不再赘述

2.借助归并排序

复杂度\(\Theta(nlogn)\)

重写归并排序的归并过程，在合并两个有序数组的过程中计数。

设待合并的两个有序数组A,B长度分别为s,t，其中长度为s的数组在前，那么这两个数组间的顺序对数可以这么计算：

先比较s和t的第一个元素A[0]和B[0]，因为题目中说两个数互异，那么有两种情况：

若A[0]<B[0]，则A[0]小于B中的所有元素，则A[0]与任何B中的元素都构成顺序对，共有t对。则这两个数组间的顺序对数=t+（A-A[0]，B这两个数组间的顺序对数）

若A[0]>B[0]，则B[0]小于A中的所有元素，则B[0]不与任何A中的元素构成顺序对。则这两个数组间的顺序对数=A，B-B[0]这两个数组间的顺序对数

无论哪种情况，都可以化成更小规模的子问题，直到有一个数组长度为0。

这样，我们就能得出这两个数组间的顺序对数。

伪代码

global count

//归并两个数列
merge(A,B):
    A_index=0
    B_index=0
    while A_index!=A.lenth and B_index!=B.lenth:
        if A[A_index].y<B[B_index].y:
            count=count+(B.lenth-B_index)
            C[A_index+B_index]=A[A_index]
            A_index=A_index+1
        else:
            C[A_index+B_index]=B[B_index]
            B_index=B_index+1
    move the left part of A or B to C
    copy C to A

mergesort(A):
    divide A into two part A1 and A2
    mergesort(A1)
    mergesort(A2)
    merge(A1,A2)

main():
    use quicksort/mergesort to sort the array by X component
    count=0
    mergesorrt(array)
    print(count)

本站总访问量次

评论