题目描述
blablabla
样例
# include<iostream>
# include<algorithm>
using namespace std;
int nums[100005];
int tmp[100005];
long res = 0;
void merge_sort(int left, int right) {
if(left >= right ) return;
int mid = left + (right - left) / 2;
merge_sort(left, mid);
merge_sort(mid + 1, right);
int i = left, j = mid + 1, k = 0;
while(i <= mid && j <= right) {
if(nums[i] > nums[j]) {
tmp[k ++] = nums[j ++];
res += (mid - i + 1);
}
else{
tmp[k ++] = nums[i ++];
}
}
while(i <= mid){
tmp[k ++] = nums[i ++];
}
while(j <= right) {
tmp[k ++] = nums[j ++];
}
for(int i = 0; i < k; i++) {
nums[left + i] = tmp[i];
}
}
int main() {
int n;
cin >> n;
for(int i = 0; i < n; i ++ ) cin >> nums[i];
merge_sort(0, n - 1);
cout << res <<endl;
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla