http://codevs.cn/problem/3286/
这里引用ssoj官网题解：
贪心+逆序对。分析如下：
对距离公式化简得：
∑(ai-bi)2=∑(ai2-2aibi+bi2)=∑ai2+∑bi2-2∑aibi，要求∑(ai-bi)2最小，就只需要∑aibi最大即可。这里有个贪心，当 a1<a2<…<an ，b1<b2<…<bn时，∑aibi最大。
证明如下：
若存在a>b，c>d，且ac+bd<ad+bc，则a(c-d)<b(c-d)，则a<b，与a>b矛盾，所以若a>b，c>d，则ac+bd>ad+bc
将此式子进行推广：
当a1<a2<a3<…<an ，b1<b2<…<bn的情况下∑aibi最大，即∑(ai-bi)2最小。
然后，将两个序列分别排序，确定每对数的对应关系，明显，同时移动两个序列中的数等效于只移动一个序列中的数，移动的时候可以将一个火柴序列不动，只移动另外一个序列。
于是可以构造一个数组C，C[i]表示最初的第i个数应该移动到C[i]位置。于是问题转换成对C[i]数组排序，每次可以交换相邻两个数，问最少需要移动多少次的问题了，也就是求这个序列的逆序对数量的问题（这里用归并排序思想实现）。
例如：
对于数据：
4
1 3 4 2
1 7 2 4
先排序:
1 2 3 4
1 2 4 7
image.jpeg
保持序列1不动，那么：
序列2中的“1”对应序列1中的位置1；
“7”对应序列1中的位置3；
“2”对应序列1中的位置4；
“4”对应序列1中的位置2，那么重定义数组c为：
image.jpeg
这个序列：1 3 4 2 的逆序对数量是 2 ，即（3,2）和(4,2)，所以答案是 2。
#include<iostream>
#include<stdio.h>
using namespace std;
#define OK 1
#define MOD 99999997
#define MAXSIZE 100010
typedef int Status;
typedef long long ll;
struct A
{
int key;
int b;
};
typedef struct
{
A *r;
int length;
}SqList;
Status InitList(SqList &L)
{
L.r=new A[MAXSIZE];
L.length=0;
return OK;
}
void MergerSort(SqList &L,SqList &T,int low,int high);
int Partition ( SqList &L,int low, int high ) ;
void QSort ( SqList &L,int low, int high ) ;
void swap(SqList &L)
{
for(int i=1;i<=L.length;i++)
{
L.r[0].key=L.r[i].key;
L.r[i].key=L.r[i].b;
L.r[i].b=L.r[0].key;
}
}
long long count=0;
int main()
{
int n;
SqList L1,L2,L3,T;
InitList(L1);
InitList(L2);
InitList(L3);
InitList(T);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>L1.r[i].key;
L1.r[i].b=i;
}
for(int i=1;i<=n;i++)
{
cin>>L2.r[i].key;
L2.r[i].b=i;
}
L1.length=n;
L2.length=n;
QSort(L1,1,L1.length);
QSort(L2,1,L2.length);
for(int i=1;i<=L1.length;i++)
{
L3.r[L2.r[i].b].b=L1.r[i].b;
}
L3.length=n;
swap(L3);
count=0;
MergerSort(L3,T,1,L3.length);
cout<<count<<endl;
return 0;
}
void MergerSort(SqList &L,SqList &T,int low,int high)
{
if(low==high)
return ;
else
{
int mid=(low+high)/2;
MergerSort(L,T,low,mid);
MergerSort(L,T,mid+1,high);
int i=low,j=mid+1,k=low;
while(i<=mid&&j<=high)
{
if(L.r[i].key<=L.r[j].key)
{
T.r[k++]=L.r[i++];
}
else
{
T.r[k++]=L.r[j++];
count=(count+mid-i+1)%MOD;
}
}
while(i<=mid)
{
T.r[k++]=L.r[i++];
}
while(j<=high)
{
T.r[k++]=L.r[j++];
}
for(int o=low;o<=high;o++)
L.r[o]=T.r[o];
}
}
void QSort ( SqList &L,int low, int high )
{ if ( low < high )
{
int pivotloc = Partition(L, low, high );
QSort(L,low,pivotloc-1);
QSort(L, pivotloc+1, high );
}
}
int Partition ( SqList &L,int low, int high )
{
L.r[0] = L.r[low];
int pivotkey = L.r[low].key;
while ( low < high )
{ while ( low < high && L.r[high].key >= pivotkey ) --high;
L.r[low] = L.r[high];
while ( low < high && L.r[low].key <= pivotkey ) ++low;
L.r[high] = L.r[low];
}
L.r[low]=L.r[0];
return low;
}
