P5149逆序对求优化方案(A了一个点然后两个WA其余全是TLE)
查看原帖
P5149逆序对求优化方案(A了一个点然后两个WA其余全是TLE)
222411
Life_passing_by楼主2022/2/26 10:46
#include<bits/stdc++.h>
using namespace std;
int ans=0;
int n,a[100010],r[100010];
string name[100010];
void msort(int s,int t)
{
	if(s==t)return;
	int mid=(s+t)/2;
	msort(s,mid);
	msort(mid+1,t);
	int i=s,j=mid+1,k=s;
	while(i<=mid&&j<=t)
	{
		if(a[i]<=a[j])
		{
			r[k]=a[i];k++;i++;
		}else{
			r[k]=a[j];k++;j++;
			ans+=mid-i+1;
		}
	}
	while(j<=mid)
	{
		r[k]=a[i];k++;j++;
	}
	for(int i=s;i<=t;i++)a[i]=r[i];
}
int main()
{
	string z;
	
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>z;
		name[i]=z;
	}
	for(int i=1;i<=n;i++)
	{
		cin>>z;
		for(int j=1;j<=n;j++)
		{
			if(name[j]==z)
			{
				a[i]=j;
			}
		}
	}
	msort(1,n);
	cout<<ans;
	return 0;
} 
2022/2/26 10:46
加载中...