描述

涵涵有两盒火柴，每盒装有 n 根火柴，每根火柴都有一个高度。现在将每盒中的火柴各自排成一列，同一列火柴的高度互不相同，两列火柴之间的距离定义为：\sum\limits_{i=1}^n (a_i-b_i)^2​i=1​∑​n​​(a​i​​−b​i​​)​2​​，其中 a_ia​i​​ 表示第一列火柴中第 i 个火柴的高度，b_ib​i​​ 表示第二列火柴中第 i 个火柴的高度。

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

格式

输入格式

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

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

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

输出格式

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

样例1

样例输入1

42 3 1 43 2 1 4

样例输出1

1

样例2

样例输入2

41 3 4 21 7 2 4

样例输出2

2

限制

每个测试点1s。

提示

###样例1说明

最小距离是 0，最少需要交换 1 次，比如：交换第 1 列的前 2 根火柴或者交换第 2 列的前 2 根火柴。

###样例2说明

最小距离是 10，最少需要交换 2 次，比如：交换第 1 列的中间 2 根火柴的位置，再交换第 2 列中后 2 根火柴的位置。

###数据范围

对于 10%的数据， 1 ≤ n ≤ 10； 

对于 30%的数据，1 ≤ n ≤ 100； 

对于 60%的数据，1 ≤ n ≤ 1,000； 

对于 100%的数据，1 ≤ n ≤ 100,000，0 ≤火柴高度≤ 2^31 − 1。

来源

NOIP 2013 提高组 Day 1

小涵涵hhhhhh

这道题凭借男人的直觉（摘自某位大佬的博客orzorz）

应该是把两个序列都排序后的值最小

事实上也是这样的

由排序不等式：

排序不等式表述如下，设有两组数a1,a2,……an和b1,b2,……bn，当满足a1≤a2≤……≤an,b1≤b2≤……≤bn则有a1bn+a2bn-1+……+anb1≤a1bt1+a2bt2+……+anbtn≤a1b1+a2b2+anbn式中t1，t2，……，tn是1，2，……，n的任意一个排列，当且仅当a1=a2=……=an或b1=b2=……=bn时成立。

一般为了便于记忆，常记为：反序和≤乱序和≤同序和.

把原式拆开(ai-bi)^2=ai^2-2aibi+bi^2

所以影响结果的只有 -aib

所以当aibi最大时原式最小

但如果直接排序（求逆序对数）会发现很明显的样例1都过不了

仔细研究后发现这里的顺序是相对的（只要保证上面的和下面的对上）

其实就是上面的那个数在a序列里排第几

下面那个数（i相等）就应该在b序列里排第几

我们要求逆序对数的序列就是b序列中的数应该排在第几位

具体可以参考这组数据（来自）

5

3 2 1 4 5

5 2 1 4 3

所以从1......n

b1应当排第5个

b2应当排第2个

b3应当排第3个

b4应当排第4个

b5应当排第1个

所以求5 2 3 4 1的逆序对

至于如何求逆序对可以参考我的文章：

#include
    
     #include
     
      #include
      
       const int mod=99999997;struct node{	int x,order;}e[100008],s[100008];int n;bool cmp(node a,node b){	return a.x
       
        =1;i-=lowbit(i))	sum+=c[i];	return sum;}int main(){	scanf("%d",&n);	for(int i=1;i<=n;i++)	scanf("%d",&e[i].x),e[i].order=i;	for(int i=1;i<=n;i++)	scanf("%d",&s[i].x),s[i].order=i;	std::sort(e+1,e+1+n,cmp);	std::sort(s+1,s+1+n,cmp);	for(int i=1;i<=n;i++)	aa[s[i].order]=e[i].order;	memset(c,0,sizeof(c));	int ans=0;		for(int i=1;i<=n;i++)	update(aa[i],1),	ans=(ans+i-getsum(aa[i]) )%mod;	printf("%d\n",ans);//	for(int i=1;i<=n;i++)	printf(	"%d ",aa[i]);	return 0;}