787 归并排序基础

  1. #include <iostream>
  2. using namespace std;
  3. const int N = 100010;
  5. int temp[N],a[N],n;
  7. void merge_sort(int a[], int l, int r){
  8.     if(l >= r)return;
  9.     int mid = (l + r) >> 1;
  10.     merge_sort(a, l, mid);
  11.     merge_sort(a, mid + 1, r);
  12.     int k = 0, i = l, j = mid + 1;
  13.     while (i <= mid && j <= r){
  14.         if(a[i] < a[j]) temp[k++] = a[i++];
  15.         else temp[k++] = a[j++];
  17.     }
  18.     while (i <= mid) temp[k++] = a[i++];
  19.     while (j <= r) temp[k++] = a[j++];
  20.     k = 0;
  21.     for(int i = l; i<=r; i++ ) a[i]=temp[k++];
  22. }
  24. int main (){
  25.     scanf("%d", &n);
  26.     for(int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
  28.     merge_sort(a, 0, n-1);
  30.     for(int i = 0; i < n; i++ )printf("%d ",a[i]);
  31.     return 0;
  32. }

788 逆序对的数量

image.png
地址：https://www.acwing.com/problem/content/790/

  1. #include <iostream>
  2. using namespace std;
  3. const int N = 100010;
  5. int temp[N];
  6. int a[N],n;
  8. long long reverseNum( int l, int r){
  9.     //在归并排序的过程中，计算逆序对
  10.     if(l >= r) return 0;
  12.     int mid = l + r >> 1;
  13.     long long num = reverseNum(l, mid) + reverseNum(mid + 1, r);// 
  15.     int k=0, i = l, j = mid + 1;
  16.     while(i <= mid && j <= r){
  17.         if(a[i] <= a[j]){//在该步骤判断是否逆序
  18.             temp[k++] = a[i++];
  19.         }else{
  20.             temp[k++] = a[j++];
  21.             num += mid - i + 1;
  22.         }
  23.     }
  25.     while(i <= mid) temp[k++] = a[i++];
  26.     while(j <= r) temp[k++] = a[j++];
  28.     for(int i = l,k = 0; i <= r; i++, k++)a[i]=temp[k];
  29.     return num;
  30. }
  34. int main(){
  35.     cin >> n;
  36.     for(int i = 0; i < n; i++ ) cin >> a[i];
  38.     cout << reverseNum(0, n-1) << endl;
  40.     return 0;
  41. }

分析

归并算法的基本思想 左右两组进行对比，即分治算法。在每次循环的时候，左右两组均为有序。自底向上，最底层的两组，即两个数字m和n，左右两组各有一个数字，这自然是有序的。自此由下往上，使用归并算法，使得每组均有序。
在求逆序数的过程中，我们只需关注，左右两组的数字作比较，即左边的某一个数字a[i]开始大于右边的a[j]，此时i到mid均大于j。

总结

思想简单，但理解起来略有难度，比较绕