【題目敘述】https://judge.tcirc.tw/ShowProblem?problemid=d064
【Tag】分治
【解題想法】
- 將所有數字置入一個vector，每次進行分治時，把數字分置於比中間數小(<=)或大(>)的兩個vectors，v1和v2。
- 當把一個新進數字放進v1時，在它之前出現且比它大的數字(即此時v2中的所有數字)，都會與其構成一組反序對(inversion)。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
long long dc(const vector<int> &v) {
int mi = *min_element(v.begin(), v.end());
int ma = *max_element(v.begin(), v.end());
if (mi == ma) return 0;
int mm = mi + (ma - mi) / 2;
vector<int> v1, v2;
long long ret = 0;
for (auto i : v) {
if (i <= mm) {
v1.push_back(i);
ret += (int)v2.size();
} else {
v2.push_back(i);
}
}
return ret + dc(v1) + dc(v2);
}
int main() {
int n;
cin >> n;
vector<int> v(n);
for (int i = 0; i < n; i++) {
cin >> v[i];
}
cout << dc(v) << "\n";
return 0;
}