欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Ural 1090. In the Army Now 解题报告

程序员文章站 2023-01-12 23:10:21
利用归并排序求逆序对数,只需要在裸体的归并排序的适当地方加上cnt=n1-i就ok了。很好理解的。   #include #includ...
利用归并排序求逆序对数,只需要在裸体的归并排序的适当地方加上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);
 }