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

問題描述

給定 k 組序列，每組長度 n。求每組的逆序對數量，輸出逆序對數量最大的那組的編號 (1-based)。

**逆序對定義**：序列中 i < j 且 a[i] > a[j] 的數對 (i, j)。

算法選擇：歸並排序 (Merge Sort)

暴力 O(n²) 超時。歸並排序合併階段天然適合統計逆序對：合併兩個有序子陣列時，若右側元素 temp2[j] 小於左側 temp1[i]，則 temp1[i...end] 全部大於 temp2[j]，一次增加 n1 - i 個逆序對。時間複雜度 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 + 1 + i];

    // 設置哨兵，簡化邊界判斷
    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
        {
            // 核心：右側元素較小，左側剩餘 (n1-i) 個元素均構成逆序對
            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;
}

關鍵點解析

1. 哨兵簡化邏輯：INF 避免合併時檢查陣列越界，代碼更簡潔。
2. 逆序對計數時機：僅在 else 分支 (取右側元素) 觸發，累加左側剩餘元素數 n1 - i。
3. 長整型防溢出：逆序對最大約 n*(n-1)/2，n=10000 時約 5e7，int 足夠；若 n 更大需用 long long。
4. 多組獨立處理：主循環遍歷 k 組，每組獨立排序統計，記錄最大值組號。

複雜度分析

• 時間：O(k * n log n)。k 組，每組歸並排序 O(n log n)。
• 空間：O(n)。合併需臨時陣列 temp1, temp2。

總結

本題是「歸並排序求逆序對」的經典模板題。關鍵在於理解合併過程中「右小左大」即產生逆序對，且數量等於左側剩餘元素個數。代碼結構清晰，哨兵技巧減少邊界判斷，是競賽編程必備技能。