解题思路:归并排序 只不过加了个记录变量ans
注意事项:
参考代码:
#include<stdio.h>
long long ans = 0;
int a[500005], b[500005], n;
void merge(int low, int mid, int high) {
int i, j, k;
for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k++) {
if (b[i] <= b[j])
a[k] = b[i++];
else {
a[k] = b[j++];
ans += mid - i + 1;
}
}
while (i <= mid) {
a[k++] = b[i++];
}
while (j <= high) {
a[k++] = b[j++];
}
for (i = low; i <= high; i++) {
b[i] = a[i];
}
}
void mergesort(int low, int high) {
if (low < high) {
int mid;
mid = (low + high) / 2;
mergesort(low, mid);
mergesort(mid + 1, high);
merge(low, mid, high);
}
}
int main() {
scanf("%d", &n);
int i;
for (i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
for (i = 1; i <= n; i++) {
b[i] = a[i];
}
mergesort(1, n);
printf("%lld", ans);
}
0.0分
2 人评分
大神老白 (C语言代码)浏览:712 |
C语言程序设计教程(第三版)课后习题7.5 (C语言代码)浏览:639 |
【出圈】 (C语言代码)浏览:553 |
【密码】 (C语言代码)浏览:333 |
打水问题 (C语言代码)浏览:1066 |
简单的a+b (C语言代码)浏览:524 |
校门外的树 (C语言代码)浏览:956 |
C语言程序设计教程(第三版)课后习题6.9 (C语言代码)浏览:994 |
C语言程序设计教程(第三版)课后习题5.7 (Java代码)浏览:885 |
C二级辅导-阶乘数列 (C语言代码)浏览:688 |