[数据结构与算法]【做题笔记】P1966 [NOIP2013 提高组] 火柴排队

题目：https://www.luogu.com.cn/problem/P1966

首先分析题目定义的距离式子：
$$\sum _{i=1}^n(a_i?b_i{)}^2$$
是不是没有头绪？

再化简一下：
$$\sum _{i=1}^n{a_i}^2?2ab+{b_i}^2$$
$$=\sum _{i=1}^n{a_i}^2+{b_i}^2?\sum _{i=1}^{n}2ab$$

很显然 ${\sum }_{i=1}^n{a_i}^2+{b_i}^2$ 是不会变的，于是要使 ${\sum }_{i=1}^n(a_i?b_i{)}^2$ 最小，让 ${\sum }_{i=1}^{n}2ab$ 最大即可。

易证很容易猜到当两个序列按升序或降序排列后，可以使 ${\sum }_{i=1}^{n}2ab$ 取最小值，这种想法是正确的（我太菜，不会严格证明）。

所以这道题就转换成：给定两个数列，要使两个数列中大小排名相等的元素一一对应（数列 $a$ 第一大的数对应数列 $b$ 第一大的数，数列 $a$ 第二大的数对应数列 $b$ 第二大的数，以此类推），求最小的交换次数。

首先定义一个结构体，$num$ 表示数组元素的值，$id$ 表示数组元素在原来序列中的位置。读入的时候记录一下 $id$，再将 $a$ $b$ 两数组升序排序。

那么该怎么求最小交换次数呢？

先来把玩一下样例二：

定义一个数组 $c$，有 $c[a[i{]}_{.id}]=b[i{]}_{.id}$

由上表可知：

$c[a[1{]}_{.id}]=b[1{]}_{.id},c[1]=1$

$c[a[2{]}_{.id}]=b[2{]}_{.id},c[4]=4$

$c[a[3{]}_{.id}]=b[3{]}_{.id},c[2]=3$

$c[a[4{]}_{.id}]=b[4{]}_{.id},c[3]=2$

所以 $c$ 数组就是 $[1,3,2,4]$（其实就是个双关键字排序）。

我们知道当 $a[i{]}_{.id}=b[i{]}_{.id}$ 时，$c_i=i$。

所以 $?i,c_i=i$ 时，$a$、$b$ 数组排序前的值的排名一一对应。

于是原问题就进一步转换成了：给定序列 $c$，每次可翻转其中两个数，求最小的翻转次数，使得序列 $c$ 升序排序。

这不就是求逆序对吗？

用归并排序就能轻松解决。

AC code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
template<class T>inline void read(T &s){
    int f=1; s=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
    s*=f;
}
const int MAXN=1e5+10;
const int md=1e8-3;
ll c[MAXN],q[MAXN],ans;
int n;
struct node{
	int num,id;
	inline void rd(int i){read(num),id=i;};
}a[MAXN],b[MAXN];
void merge_sort(int l,int r){
	if(l==r) return;
	int mid=(l+r)>>1;
	merge_sort(l,mid),merge_sort(mid+1,r);
	int head1=l,head2=mid+1;
	for(int i=l;i<=r;i++){
		if(head2<=r&&(head1>=mid+1||c[head1]>c[head2]))
			q[i]=c[head2++];
		else q[i]=c[head1++],ans+=(head2-mid-1)%md; 
	} 
	for(int i=l;i<=r;i++) c[i]=q[i];
}
inline bool cmp(const node&x,const node&y){
	return x.num<y.num;
}
signed main(){
	ios::sync_with_stdio(false);
	read(n);
	for(int i=1;i<=n;i++) a[i].rd(i);
	for(int i=1;i<=n;i++) b[i].rd(i);
	sort(a+1,a+n+1,cmp); sort(b+1,b+n+1,cmp);
	for(int i=1;i<=n;i++)
		c[a[i].id]=b[i].id;
	merge_sort(1,n);
	cout<<ans%md;
	return 0;
} 

完结撒花~