Ural 1090. In the Army Now 解題報告

利用歸並排序求逆序對數，只需要在裸體的歸並排序的適當地方加上cnt=n1-i就OK了。很好理解的。
 
#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, n2;
     n1 = mid - start + 1;
     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];
             i++;
         }
         else
          {
              cnt+=n1-i;//逆序對的個數
             array[k] = temp2[j];
             j++;
         }
     }
 }
 www.2cto.com
 // 歸並排序
 void MergeSort(int array[], int start, int end)
  {
     if (start < end)
      {
         int i;
         i = (end + start) / 2;
         // 對前半部分進行排序
         MergeSort(array, start, i);
         // 對後半部分進行排序
         MergeSort(array, i + 1, end);
         // 合並前後兩部分
         Merge(array, start, i, end);
     }
 }
 
 int main()
 {
     int n,k;
     int arr[MAXM];
     int largemerge=0;
     int num;
     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);
 }