帮我写完整的C语言代码解决如下问题:给定一个数组 Data 包含N个元素。如果 0≤ i < j < N 且 Data[i] > 2*Data[j] ,则 (i, j) 称作一个重要反序对。 请返回给定数组中的重要反序对的数量。 输入格式: 用 [、]和 , 分隔表示的数组。如:[1,2,3,4,5] 输出格式: 输出一个整数,表示数组中重要反序对的数量。 输入样例: [1,3,2,3,1] 输出样例: 2
时间: 2024-02-19 21:02:45 浏览: 73
c语言编程题之数组操作下一个更大的元素.zip
好的,下面是完整的 C 语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_N 100000
int data[MAX_N];
int tmp[MAX_N];
long long res;
void merge_sort(int start, int end) {
if (start >= end) {
return;
}
int mid = (start + end) / 2;
merge_sort(start, mid);
merge_sort(mid + 1, end);
// 统计跨越左右两个子数组的逆序对数量
int i = start, j = mid + 1;
while (i <= mid && j <= end) {
if (data[i] > 2 * data[j]) {
res += mid - i + 1;
j++;
} else {
i++;
}
}
// 归并两个有序子数组
i = start, j = mid + 1;
int k = 0;
while (i <= mid && j <= end) {
if (data[i] <= data[j]) {
tmp[k++] = data[i++];
} else {
tmp[k++] = data[j++];
}
}
while (i <= mid) {
tmp[k++] = data[i++];
}
while (j <= end) {
tmp[k++] = data[j++];
}
memcpy(data + start, tmp, sizeof(int) * k);
}
int important_reverse_pairs(char* input) {
// 读入数组
int n = 0;
char* p = strtok(input, "[,]");
while (p) {
data[n++] = atoi(p);
p = strtok(NULL, "[,]");
}
// 归并排序,并统计逆序对数量
res = 0;
merge_sort(0, n - 1);
return res;
}
int main() {
char input[1000];
fgets(input, sizeof(input), stdin);
input[strlen(input) - 1] = '\0';
printf("%d\n", important_reverse_pairs(input));
return 0;
}
```
输入的数组从标准输入中读入,输出结果到标准输出。算法的时间复杂度为 $O(n \log n)$,其中 $n$ 是输入数组的长度。
阅读全文