社区讨论

0分,求调

P1908逆序对参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@mcbb65a4
此快照首次捕获于
2025/06/25 10:01
8 个月前
此快照最后确认于
2025/11/04 07:29
4 个月前
查看原帖
CPP
#include <bits/stdc++.h>
using namespace std;
int a;
long long n[10000000];
long long tem[10000000];

int y = 0;
void merge_sort( int l, int r) {
	if (l >= r)
		return ;
	int mid = l + r >> 1;

	merge_sort( l, mid);
	merge_sort( mid + 1, r);

	int i = l, j = mid + 1, k = 0;
	while (i <= mid && j <= r)
		if (n[i] > n[j] && i < j) {
			y++;


		}
	if (n[i] < n[j]) {
		tem[k ++] = n[i ++];

	} else {
		tem[k ++] = n[j ++];

	}
	while (i <= mid)
		tem[k ++] = n[i ++];
	while (j <= r)
		tem[k ++] = n[j ++];


	for (int i = l, j = 0; i <= r; i ++, j ++) {
		n[i] = tem[j];
	}

	return ;
}

int main() {
	cin >> a;
	for (int i = 0; i < a; i++) {
		cin >> n[i];
	}
	merge_sort(0, a - 1);
//	for (int i = 0; i < a; i ++)
//		cout << n[i] << ' ';
	cout << y ;
	return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...