脚本宝典收集整理的这篇文章主要介绍了求逆序对(介绍+题目)，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

介绍

逆序对 - 如果存在l<r，并且a[l]<a[r]，则称为一个逆序对。 在稳定排序情况下,逆序对的个数等于相邻数交换的次数。(可以说是冒泡的次数) 至于你说你冒泡排序,归并排序(后面要用)都不太会建议去看看,鄙人的文章 各种排序集合 ps:并不是打广告,这是为了您好.)逃

个人看法

相信很多人跟 以前的我 一样认为逆序对不难,归并排序一下就出来了,多简单啊! 但我想说,简单是简单,但是大部分题目你都看不出来,所以 偶 才写了这篇文章

题目

P5149 会议座位

题目描述

话说校长最近很喜欢召开全校教职工大会，让老师们强行听他装逼

现在校长在校园网上公布了一份座位表，(n) 位老师从左到右依次排成一行。老师们都对这个座位很满意。

然而到了开会时，校长不小心把座位表打乱了，老师们很不满。老师们并不在意自己的位置变了多少，但如果有一对老师 (a) 和 (b)，他们原来的座位是 (a) 在 (b) 左边，现在变成了 (a) 在 (b) 右边，那么这一对老师便会有一单位不满值。

校长想知道这些老师的总不满值是多少。

输入介绍

第一行一个正整数 (n)，为 (n) 位老师。

第二行有 (n) 个字符串，每个字符串代表老师的名字（大小写敏感）。这一行代表原来的座位表。

第三行有 (n) 个字符串，代表打乱后的座位表。

输出介绍

一行，一个正整数，表示老师们的总不满值。

输入输出样例

样例1:
3                                                                    1
Stan Kyle Kenny                                                      
Kyle Stan Kenny                                                      

样例2:
5                                                                    3
A B C D E
B A D E C

解析

只要看清本质就会了,就是求逆序对 用归并排序就可以了

程序

由于个人 马 蜂 不好看所以用一个"盆友"的

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

const int N=1e5+5;
string s;
int n,a[N],b[N];
long long ans;
map<string,int>m;

void merge_sort(int left,int right)
{
	if(left>=right) return;
	int mid=(right-left)/2+left;
	merge_sort(left,mid);
	merge_sort(mid+1,right);
	int i=left,j=mid+1,k=left;
	while(i<=mid&&j<=right)
	{
		if(a[i]<a[j]) b[k++]=a[i++];
		else b[k++]=a[j++],ans+=mid-i+1;
	}
	while(i<=mid) b[k++]=a[i++];
	while(j<=right) b[k++]=a[j++];
	for(int i=left;i<=right;i++)
		a[i]=b[i];
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		cin>>s;
		m[s]=i;
	}
	for(int i=1;i<=n;i++)
	{
		cin>>s;
		a[m[s]]=i;
	}
	merge_sort(1,n);
	printf("%lld",ans);
	return 0;
}

脚本宝典总结

以上是脚本宝典为你收集整理的求逆序对(介绍+题目)全部内容，希望文章能够帮你解决求逆序对(介绍+题目)所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。