题目描述
blablabla
样例
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <vector>
/*
1.对于逆序对问题,小规模可以用冒泡计数,大规模可以用归并排序
*/
using namespace std;
int arr[100005];
int tmp[100005];
long long cnt = 0;
long long ans = 0;
void merge_sort(int l, int r)
{
if (l >= r)
return;
int mid = (l + r) >> 1;
merge_sort(l, mid);
merge_sort(mid + 1, r);
int a = l;
int b = mid + 1;
int cnt = 0;
while (a <= mid && b <= r)
if (arr[a] <= arr[b])
tmp[cnt++] = arr[a++];
else
{
tmp[cnt++] = arr[b++];
ans += mid - a + 1;
}
while (a <= mid)
tmp[cnt++] = arr[a++];
while (b <= r)
tmp[cnt++] = arr[b++];
for (int i = l, j = 0; i <= r; i++, j++)
arr[i] = tmp[j];
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
for (int i = 0; i < n; i++)
cin >> arr[i];
merge_sort(0, n - 1);
cout << ans;
return 0;
}
//冒泡太慢
/*
int arr[100005];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
for (int i = 0; i < n;i++)
cin >> arr[i];
long long cnt = 0;
for (int i = 1; i <= n;i++)
{
int flag = 0;
for (int j = 0; j < n - i ;j++)
{
if(arr[j]>arr[j+1])
{
cnt++;
flag = 1;
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
if(!flag)
break;
}
cout << cnt;
return 0;
}
*/
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla