Luogu火柴排队

2017-08-06

火柴排队

题目描述

涵涵有两盒火柴，每盒装有 n 根火柴，每根火柴都有一个高度。 现在将每盒中的火柴各自排成一列， 同一列火柴的高度互不相同， 两列火柴之间的距离定义为： ∑(ai-bi)^2

其中 ai 表示第一列火柴中第 i 个火柴的高度，bi 表示第二列火柴中第 i 个火柴的高度。

每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离，最少需要交换多少次？如果这个数字太大，请输出这个最小交换次数对 99,999,997 取模的结果。

输入输出格式

输入格式： 输入文件为 match.in。

共三行，第一行包含一个整数 n，表示每盒中火柴的数目。

第二行有 n 个整数，每两个整数之间用一个空格隔开，表示第一列火柴的高度。

第三行有 n 个整数，每两个整数之间用一个空格隔开，表示第二列火柴的高度。

输出格式： 输出文件为 match.out。

输出共一行，包含一个整数，表示最少交换次数对 99,999,997 取模的结果。

思路

方案很好想，匹配的两个火柴棒，在各自的组别中按大小关系排序后的序号应该

是相同的，虽然证明比较麻烦，但是符合人类直觉…很多时候符合人类直觉就

好了啊…..

求步数来说直接就想到了逆序对，然后发现根本不会搞23333

可以假定一组火柴棒来做模板（比如A），那么和这条火柴棒匹配的一定是与这个火柴棒在大小排名上相同的火柴棒，那么可以把两者都按照大小排个序，对于序号相同的火柴棒，必须要把B挪过来使之对应，然后我们就得到了我们要移动成的目标状态，与之对应的初始状态是1,2,3…..n，而移动成我们想要的状态就是那个状态的逆序对数

代码

#define mod 99999997
#include<algorithm>
#include<iostream>
#include<cstdio>
#define N 100010
using namespace std;
int n;
int f[N];
int d[N],ans;
struct node
{
	int id,num;
}a[N],b[N];
bool comp(node aa,node bb)
{
	return aa.num<bb.num;
}
int low(int now)
{
	return now&(-now);
}
void add(int now,int it)
{
	for(int i=now;i<=n;i+=low(i))
	{
		f[i]+=it;
	}
}
int ask(int now)
{
	int re=0;
	for(int i=now;i;i-=low(i))
	{
		re+=f[i];
		re%=mod;
	}
	return re;
}
void doit()
{
	for(int i=1;i<=n;++i)
	{
		add(d[i],1);
		ans+=(i-ask(d[i]));
		ans%=mod;
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&a[i].num);
		a[i].id=i;
	}
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&b[i].num);
		b[i].id=i;
	}
	sort(a+1,a+n+1,comp);
	sort(b+1,b+n+1,comp);
	for(int i=1;i<=n;++i)
	{
		d[a[i].id]=b[i].id;
	}
	doit();
	printf("%d",ans);
	return 0;
}
Comment Box
(update the code to your comment plugin in comment-full.html)