*[codility]ArrayInversionCount

http://codility.com/demo/take-sample-test/arrayinversioncount

求逆序对数,归并排序并记录逆序次数。

// you can also use includes, for example:
// #include <algorithm>
int merge(vector<int> &A, int left, int right) {
if (left >= right) return 0;
int mid = left + (right - left) / 2;
int left_count = merge(A, left, mid);
int right_count = merge(A, mid + 1, right);
vector<int> tmp;
int i = left;
int j = mid + 1;
int merge_count = 0;
while (i <= mid || j <= right) {
if (i <= mid && j <= right) {
if (A[i] > A[j]) {
tmp.push_back(A[i++]);
merge_count += (right - j + 1);
}
else {
tmp.push_back(A[j++]);
}
}
else if (i <= mid) {
tmp.push_back(A[i++]);
}
else {
tmp.push_back(A[j++]);
}
}
for (int k = 0; k < tmp.size(); k++) {
A[left + k] = tmp[k];
}
return (left_count + right_count + merge_count);
} int solution(const vector<int> &A) {
// write your code in C++98
vector<int> B(A);
return merge(B, 0, B.size() - 1);
}

  

上一篇:SAE下的Memcache使用方法


下一篇:CentOS7 安装Mono及Jexus