题解 P1774 【最接近神的人】
为什么是逆序对
逆序对的做法已经有很篇题解讲的很好了。但是很少题解有讲为什么相邻交换的次数就是逆序对。这篇题解只是为了证明这个。
首先，显然排好序的序列逆序对数一定是 0。
对于i, 和i+1, 显然如果a[i] <= a[i+1] 那么交换这两个数是多余的。因为不管后面怎么交换，最终a[i]一定在a[i+1]前面，如果交换这两个，就会增加a[i]到a[i+1]的前面的交换次数。
对于i,和j, 设i<j且a[i] > a[j], 那么最终a[j]会交换到a[i]前面, 因为只能两两相邻交换，a[i]和a[j]肯定也会交换，否则a[j]无法到a[i]前面, 因为a[j]不可能跳过a[i]。
交换两个相邻的数逆序对数会 -1。显然若a[i] > a[i+1] 交换是它们会减少1个逆序对，由于a[i]和a[i+1]中间没有数，所以不会影响其他逆序对。导致逆序对数会减少1。
既然，任意两个逆序对都要交换，并且每次交换后逆序对数都会减少1，最终的逆序对数是0，那么肯定要交换的个数就是全部逆序对的个数。