这个答案不对啊,[1,3,2,3,1]输入应该输出2,修改一下代码吧
时间: 2024-03-07 19:50:45 浏览: 22
非常抱歉,我的回答有误。下面是修改后的代码:
```c
#include <stdio.h>
#include <stdlib.h>
int merge(int *arr, int *tmp, int left, int mid, int right)
{
int i = left, j = mid + 1, k = left, count = 0;
while (i <= mid && j <= right) {
if ((long long)arr[i] > 2 * (long long)arr[j]) {
count += mid - i + 1; //统计逆序对
j++;
} else {
i++;
}
}
i = left, j = mid + 1;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
tmp[k++] = arr[i++];
} else {
tmp[k++] = arr[j++];
}
}
while (i <= mid) tmp[k++] = arr[i++];
while (j <= right) tmp[k++] = arr[j++];
for (i = left; i <= right; i++) {
arr[i] = tmp[i];
}
return count;
}
int merge_sort(int *arr, int *tmp, int left, int right)
{
if (left >= right) return 0;
int mid = (left + right) / 2;
int count = merge_sort(arr, tmp, left, mid) + merge_sort(arr, tmp, mid + 1, right) + merge(arr, tmp, left, mid, right);
return count;
}
int main()
{
char c;
int n = 0, i = 0;
scanf("%c", &c);
while (c != ']') {
if (c >= '0' && c <= '9') {
n++;
}
scanf("%c", &c);
}
int *arr = (int *)malloc(sizeof(int) * n);
int *tmp = (int *)malloc(sizeof(int) * n);
scanf("%c", &c);
while (c != ']') {
if (c >= '0' && c <= '9') {
arr[i++] = c - '0';
while ((c = getchar()) >= '0' && c <= '9') {
arr[i - 1] = arr[i - 1] * 10 + c - '0';
}
}
scanf("%c", &c);
}
printf("%d\n", merge_sort(arr, tmp, 0, n - 1));
free(arr);
free(tmp);
return 0;
}
```
修改后的代码中,首先使用循环读取输入,统计数组的长度。然后再次循环读取输入,将输入的数字存入数组中。在统计逆序对的时候,需要将相乘的两个数强制转换为 long long 类型,以避免溢出。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)