来源：算法课OJ题
题目
Problem Description
Recall the problem of finding the number of inversions. As in the course, we are given a sequence of nn numbers a1,a2,⋯,ana1,a2,⋯,an, and we define an inversion to be a pair i<ji<j such that ai>ajai>aj.
We motivated the problem of counting inversions as a good measure of how different two orderings are. However, one might feel that this measure is too sensitive. Let’s call a pair a significant inversion if i<ji<j and ai>3ajai>3aj. Give an O(nlogn)O(nlogn) algorithm to count the number of significant inversions between two orderings.
The array contains N elements (1<=N<=100,000). All elements are in the range from 1 to 1,000,000,000.
Input
The first line contains one integer N, indicating the size of the array. The second line contains N elements in the array.
- 50% test cases guarantee that N < 1000.
Output
Output a single integer which is the number of pairs of significant inversions.
Sample Inout
|
1 2 |
6 13 8 5 3 2 1 |
Sample Output
|
1 |
6 |
翻译一下：
求逆序对，要求是满足i<j，且ai>3*aj。案例中(13,3) (13,2) (13,1) (8,2) (8,1) (5,1)共6组
思路
对于常规逆序对问题，我们可以常常可以采用两种方式去解决。
其一：采用暴力法，即轮询，但是这样的时间复杂度在n^2，显然不符合题目要求
其二：归并排序的思想，由于在归并排序中，例如[13,8,5,3]，归并排序的思想是分而治之，先分==》即[13,8][5,3]，再分==》[13][8][5][3]，再治==》对于[13][8]由于13>8，故先放8，后放13，此时也就说明8与13是逆序之间的关系，同理[3,5]，再治==》对于[8,13][3,5]，左右两个数组都是有序数组了，因此先从第一个开始判断8>3，所以先放3，且count+=2，因为这也就说明了3肯定比8和13都要大，而在一开始3在8与13后面，所以肯定有两个逆序对，以此类推。
Trick
本道题有两个耐人寻味的地方
其一，在判断ai>3*aj时，由于样例中3*aj有可能会发生溢出，因此我们可以变换成ai-aj>2*aj来判断
其二，由于传统的归并排序仅需要判断一倍的大小就可，但是题目中是判断3倍的关系，即对于[8,3]这个样本，归并处理会认为存在逆序对，但是实际上8<3*3，所以不存在题目中要求的3倍关系的逆序对，因此在归并的时候，右边数组确定完一个基数后，要在左边数组采用二分查找的方式去查找等于3倍基数的位置。（不采用二分查找，也可以遍历，但是在OJ系统上会超时）
解法
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
#include <stdlib.h> #include <stdio.h> int dataIn[1000000], dataTemp[1000000], n, count = 0; int bigData(int data[], int left, int right,int num) { if (left >= right) { if (data[left] - num < 2 * num) { return left + 1; } else if(data[left] - num == 2 * num){ return left + 1; } else { return left; } } int mid = (left + right) >> 1; if (data[mid]-num < 2*num) { return bigData(data, mid + 1,right,num); } else if (data[mid]-num == 2*num) { return mid+1; } else { return bigData(data, left, mid - 1,num); } } void mergeSort(int left, int right, int data[]) { if (left >= right)return; int mid = (left + right) >> 1; mergeSort(left, mid, data); mergeSort(mid + 1, right, data); int l = left, r = mid + 1, pos = 0; while (l <= mid && r <= right) { if (data[l] <= data[r]) { dataTemp[pos++] = data[l++]; } else { /*for (int k = mid; k >= l; k--) { if ((data[k] - data[r]) > 2 * data[r]) { count++; } }*/ count += (mid - bigData(data, l, mid, data[r])+1); dataTemp[pos++] = data[r++]; } } while (l <= mid) { dataTemp[pos++] = data[l++]; } while (r <= right) { dataTemp[pos++] = data[r++]; } for (int i = 0; i < pos; i++) { data[left + i] = dataTemp[i]; } } int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &dataIn[i]); } mergeSort(0, n - 1, dataIn); printf("%d", count); return 0; } |
