【挑战程序设计竞赛】分治法求一个数列逆序对的对数
此题来源于冒泡排序需要交换的次数，在冒泡排序中，我们需要交换两个元素的位置的情况是：对于位置
(i<j)有a[i]>a[j]，我们称这是一对逆序数，我们就要求一个数列中满足这样条件的对数，当然采用暴力法两重的
for循环当然可以做到，复杂度是O(n^2)，我们采用分治法，类似于合并排序的思想：
#include <iostream>#include <vector>using namespace std;typedef long long LL;LL merge_cnt(vector<int> &input){int n = input.size();if(n <= 1) return 0;LL cnt = 0;vector<int> left(input.begin(),input.begin() + n/2); //划分 vector<int> right(input.begin() + n/2,input.end());cnt += merge_cnt(left);cnt += merge_cnt(right);int ai = 0, bi = 0, ci = 0;while(ai < n){if(bi < left.size() && (ci == right.size() || left[bi] <= right[ci])){input[ai++] = left[bi++];}else{cnt += n/2 - bi; // 对于数列right的每一个元素，统计left中 // 大于此元素的个数，此时两个数列是已经排好序的 input[ai++] = right[ci++];}}return cnt;} int main(){int a[4]={3,1,4,2};vector<int> input(a,a+4);cout<<merge_cnt(input)<<endl;for(int i = 0; i < input.size(); i++){cout<<input[i]<<" ";}cout<<endl;}