AI题库 · 信息学奥赛-提高级题库
题目分享 #22540
#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
输出:_________
AI题库 · 编程考级与信奥赛真题库
查看答案 →
复制链接后可在微信、QQ、小红书等平台粘贴分享;答案与解析在题目页。