QQ扫一扫联系
#include<iostream>
using namespace std;
int n, s, a[100005], t[100005], i;
void mergesort(int l, int r) {
if (l == r)
return;
int mid = (l + r) / 2;
int p = l;
int i = l;
int j = mid + 1;
mergesort(l, mid);
mergesort(mid + 1, r);
while (i <= mid && j <= r) {
if (a[j] < a[i]) {
s += mid - i + 1;
t[p] = a[j];
p++;
j++;
} else {
t[p] = a[i];
p++;
i++;
}
}
while (i <= mid) {
t[p] = a[i];
p++;
i++;
}
while (j <= r) {
t[p] = a[j];
p++;
j++;
}
for (i = l; i <= r; i++)
a[i] = t[i];
}
int main() {
cin >> n;
for (i = 1; i <= n; i++)
cin >> a[i];
mergesort(1, n);
cout << s << endl;
return 0;
}输入：
6
2 6 3 4 5 1
输出：_________
