C++Problem A 最少的交换?

Question

现在给你一个由n个互不相同的整数组成的序列，现在要求你任意交换相邻的两个数字，使序列成为升序序列，请问最少的交换次数是多少？输入包含多组测试数据。每组输入第一行是一个正整数n（n<500000），表示序列的长度，当n=0时。
接下来的n行，每行一个整数a[i]（0<=a[i]<=999999999），表示序列中第i个元素。对于每组输入，输出使得所给序列升序的最少交换次数。这里void MergeSort(int a[],int start,int end)函数中的start和end不都是具体的数吗，第一次start=0,end=n-1，但是始终start<end,MergeSort(a,start,mid),MergeSort(a,mid+1,end),始终start<mid,mid+1<end,所以怎么说就把两个部分交换了呢？交换的不应该是a[i]吗，怎么变成了比较两个已有大小的数？

 

Answer 1

这个题目求的是逆序数，而并不是排序，所以并不需要交换数组里面的数据。你百度下逆序数是什么东西你就知道这个题目为什么可以通过求逆序数来达到效果。