Ural 1090 "In the Army Now" 解題報告：歸並統計逆序對

問題建模

給定 k 個長度為 n 的排列，找出逆序對數量最多的那個排列的編號。利用歸並排序過程中統計逆序對，複雜度 O(n log n)。

核心算法：歸並排序計數逆序對

#include <cstdio>
#include <iostream>
using namespace std;

const int MAXM = 10003;
const int INF = 0x7fffffff - 1;
int cnt;

void Merge(int array[], int start, int mid, int end) {
    int temp1[MAXM/2+1], temp2[MAXM/2+1];
    int n1 = mid - start + 1;
    int n2 = end - mid;

    for (int i = 0; i < n1; ++i) temp1[i] = array[start + i];
    for (int i = 0; i < n2; ++i) temp2[i] = array[mid + i + 1];
    temp1[n1] = temp2[n2] = INF;

    for (int k = start, i = 0, j = 0; k <= end; ++k) {
        if (temp1[i] <= temp2[j]) {
            array[k] = temp1[i++];
        } else {
            cnt += n1 - i;  // 關鍵：右邊元素插隊，左邊剩餘全部構成逆序對
            array[k] = temp2[j++];
        }
    }
}

void MergeSort(int array[], int start, int end) {
    if (start < end) {
        int mid = (start + end) / 2;
        MergeSort(array, start, mid);
        MergeSort(array, mid + 1, end);
        Merge(array, start, mid, end);
    }
}

int main() {
    int n, k;
    int arr[MAXM];
    int largemerge = 0, num = 0;
    scanf("%d %d", &n, &k);
    for (int j = 1; j <= k; ++j) {
        cnt = 0;
        for (int i = 0; i < n; ++i) scanf("%d", arr + i);
        MergeSort(arr, 0, n - 1);
        if (cnt > largemerge) {
            largemerge = cnt;
            num = j;
        }
    }
    printf("%d\n", num);
    return 0;
}

關鍵點解析

• 歸並合併時，若右半部元素 temp2[j] 小於左半部 temp1[i]，則左半部從 i 到末尾的所有元素都與之構成逆序對，數量為 n1 - i。
• 哨兵 INF 簡化邊界判斷。
• 多組數據獨立處理，記錄最大逆序對對應的組號。