改了一点,0分 归并+排序 求助!!!(急)
查看原帖
改了一点,0分 归并+排序 求助!!!(急)
494699
卷王慢即快楼主2022/12/12 21:08

悬赏关注!!!!!!!!!!

#include <cstdio>
#include <algorithm>
using namespace std;
#define mod 9999997
int n;
struct node
{
	int high, num;
}a[100001], b[100001];
long long t[100001], mp[200001];
long long ans = 0;
inline int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9')
	{
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	return x * f;
}
inline bool cmp(node x, node y)
{
	return x.high < y.high;
}
inline void qsort(int l, int r)
{
	if(l == r) return;
	int mid = (l + r) >> 1;
	qsort(l, mid);
	qsort(mid + 1, r);
	int i, j = l, k = mid + 1;
	while(j <= mid && k <= r)
	{
		if(mp[j] <= mp[k]) t[i++] = mp[j++];
		else t[i++] = mp[k++], ans = (ans + mid - j + 1) % mod;
	}
	while(j <= mid)
		t[i++] = mp[j++];
	while(k <= r)
		t[i++] = mp[k++];
	for(i = l; i <= r; i++)
		mp[i] = t[i];
}
int main()
{
	n = read();
	for(int i = 1; i <= n; i++)
	{
		a[i].high = read();
		a[i].num = i;
	}
	for(int i = 1; i <= n; i++)
	{
		b[i].high = read();
		b[i].num = i;
	}
	sort(a + 1, a + n + 1, cmp);
	sort(b + 1, b + n + 1, cmp);
	for(int i = 1; i <= n; i++)
		mp[b[i].num] = a[i].num;
	qsort(1, n);
	printf("%ld", ans);
	return 0;
}

全WA。

2022/12/12 21:08
加载中...