Comment

zysvvv: 2025-05-24 23:10:52

这个python没超时

def mergeSort_and_count(nums):
    if len(nums)==1:
        return nums

    mid=int(len(nums)/2)

    global count
    left=mergeSort_and_count(nums[:mid])
    right=mergeSort_and_count(nums[mid:])

    i=j=0
    result=[]
    while i<len(left) and j<len(right):
        if left[i]<=right[j]:
            result.append(left[i])
            i+=1
        else:
            result.append(right[j])
            j+=1
            count+=len(left)-i
    if i==len(left):
        result.extend(right[j:])
    else:
        result.extend(left[i:])

    return result


m=int(input())
for _ in range(m):
    nums=list(map(int,input().split()))
    n=nums[0]
    nums=nums[1::]
    count=0
    result=mergeSort_and_count(nums)
    print(count)

Jiang212: 2025-04-17 16:46:37

//一个非常典型的归并排序的应用，由于是否逆序对只与两者的相对大小关系有关，应用归并排序的原理，我们可以在排序与的过程中计算逆序对的个数
#include <iostream>

using namespace std;
const int N = 50010;
int q[N];//数组 
int ans;
int temp[N];

void merge_sort(int l, int r, int q[])
{
	if(l >= r) return;
	
	int mid = l + r >> 1;
	merge_sort(l, mid, q), merge_sort(mid + 1, r, q);
	int i = l, j = mid + 1, k = 0;
	while(i <= mid && j <= r)
	{
		if(q[i] <= q[j]) temp[k ++ ] = q[i ++];
		else
		{
			temp[k ++] = q[j ++];
			ans += (mid - i + 1);//q[j]与q[l~i]都可以组成逆序对 
		}
	}
	//将剩余数组加到后面 
	while(i <= mid) temp[k ++ ] = q[i ++];
	while(j <= r) temp[k ++] = q[j ++];
	
	for(i = l, j = 0; i <= r; i ++, j ++)
		q[i] = temp[j];
}

int main()
{
	int T;
	cin >> T;
	while(T -- )
	{
		int n;
		cin >> n;
		for(int i = 0; i < n; i ++) cin >> q[i];
		ans = 0;
		merge_sort(0, n - 1, q);
		
		cout << ans << endl; 
	}
}

Huhu_Miao: 2025-04-17 15:20:38

/**
 *    author:  Huhu_Miao
 *    created: 2025.4.17 15:20:00 (UTC+8)
**/
#include<iostream>

int arr[50010];

int merge_and_count(int nums[] , int lo , int hi){//[lo , hi)
	if(hi - lo <= 1) return 0;
	int mid = (lo + hi)/2;
	int cnt1 = merge_and_count(nums , lo , mid) , cnt2 = merge_and_count(nums , mid , hi), cnt3 = 0;
	int * temp = new int[ hi - lo ];

	int i = lo , j = mid , k = 0;
	while(i < mid && j < hi){
		if(nums[j] < nums[i]){
			temp[k++] = nums[j++];
			cnt3 += (mid - i);
		}else{
			temp[k++] = nums[i++];
		}
	}
	while(i<mid) temp[k++] = nums[i++];
	while(j<hi) temp[k++] = nums[j++];

	for(int i = lo ; i < hi ; i++) nums[i] = temp[i - lo];
	delete[] temp;
	return cnt1 + cnt2 + cnt3;
}

void solve(){
	int n; std::cin >> n;
	for(int i = 0 ; i < n ; i++) std::cin >> arr[i];
	std::cout << merge_and_count(arr,0,n) << '\n';
}

int main(){
	std::ios::sync_with_stdio(false); std::cin.tie(nullptr);
	int T; std::cin>>T;
	while(T--) solve();
	return 0;
}

Batman: 2025-01-08 17:07:42

python归并方法  超时

Three thousand times in a dream: 2024-09-24 18:12:28

用Python写，O(nlogn)都超时

CyanFish: 2022-06-25 16:38:05

归并排序 + 一句

CyanFish: 2022-06-25 16:37:23

```cpp
#include <iostream>
```