求助
  • 板块灌水区
  • 楼主jzy_CSPJ_AK
  • 当前回复4
  • 已保存回复5
  • 发布时间2024/12/7 09:37
  • 上次更新2024/12/28 21:13:48
查看原帖
求助
1034698
jzy_CSPJ_AK楼主2024/12/7 09:37

逆序对代码:

#include<bits/stdc++.h>
using namespace std;

const int N = 5e5 + 5;

int a[N], n;
long long ans;

void merge_sort(int a [], int n){ // 分解函数 
	int tmp[N];
	for(int i = 1; i < n;i <<= 1){
		for(int l = 0; l < n - i;l += 2 * i){
			int r = l + i;
      		int l2 = r;
      		int r2 = min(l2 + i, n);
      		merge(a + l, a + r, a + l2, a + r2, tmp + l);
      		for (int i = l; i < r2; ++i) a[i] = tmp[i];
		}
	}
}
void merge(int a [], int aLen, int b [], int bLen, int *c) { // 合并函数 
  	int i = 0, j = 0, k = 0;
  	while (i < aLen && j < bLen) {
    	if (b[j] < a[i]) c[k] = b[j ++], ans += (aLen - i + 1);
    	else c[k] = a[i ++];
    	++k;
//    	cout << i << " " << j << " " << aLen << " " << bLen << " " << k << endl;
  	}
  	for (; i < aLen; ++i, ++k) c[k] = a[i];
  	for (; j < bLen; ++j, ++k) c[k] = b[j];
}

int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin >> n;int op;
	while(cin >> op){
		ans = 0;
        a[0] = op;
		for(int i = 1;i < n;i ++){
			cin >> a[i];
		}	
		merge_sort(a, n);// 分解 
		cout << ans << endl;
	}
	
	
	return 0;
} 

逆序对数量一直是0,大佬们看看怎么办

2024/12/7 09:37
加载中...