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);
 }