UVa 299 列车调度

思路：好吧，这是一道水题。。（这样说是不是太不好了？）主要就是求逆序对数，即 i<j 而 a[i]>a[j]的总个数

           记得算法导论里分治法排序那部分有提到逆序对问题。本来打算用分治法的，发现这题规模比较小，而且按照白书的安排，好像暂时不需要这样的算法~结果直接O（n2）的算法就过了~

Code：

#include<stdio.h>
#define N 55

int num[N];

int main()
{
 int n;
 int el;
 scanf("%d",&n);
 while(n-->0)
 {
  scanf("%d",&el);
  for(int i=0;i<el;++i)
   scanf("%d",&num[i]);      
   
  int cnt=0;
  for(int i=0;i<el;++i)
   for(int j=i+1;j<el;++j)
   {
    if(num[i]>num[j])
     cnt++;       
   }     
   
  printf("Optimal train swapping takes %d swaps.\n",cnt);              
 }//while   
 return 0;
}

UVa 299 列车调度,布布扣,bubuko.com

UVa 299 列车调度

原文：http://blog.csdn.net/buxizhizhou530/article/details/21130479