自动搬运

查看原文

来自洛谷，原作者为

	yx666 幸会，OI。OI，幸会 。

搬运于2025-08-24 22:27:33，当前版本为作者最后更新于2024-05-12 12:53:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

P7194 CESTARINE 题解

原题面传送门

Part 1：题意

Part 1.1：题目内容

给定两个长度为 $n$ 的数列 $a$ 和 $b$，满足同一数列中元素互不相同（$a$ 对应题目中所有的入口，$b$ 对应所有的出口）。

求将数列 $a$ 随机打乱后，并满足 $\forall i\in[1,n]$，$a_i\ne b_i$ 时，$\sum_{i=1}^n \left|a_i-b_i\right|$ 的最小值。

Part 1.2：限制

• $n\in[1,10^5]$。

• $\forall i\in[1,n],a_i,b_i\in[1,10^6]$。

• 时间：$1$ s，空间 $32$ MB，所有输入均为整数。

Part 2：思路

考虑 dp。

Part 2.1：定义问题状态

对 $a$、$b$ 进行排序，接着设 $f_k$ 表示将前 $k$ 个出入口配对后的花费最小值，即：

$$f_k=\begin{cases}\sum_{i=1}^k \left|a_i-b_i\right|\qquad&\forall i\in[1,k]，a_i\ne b_i \\\inf &\text{otherwise} \end{cases}$$

Part 2.2：状态转移方程

定义函数 $ckabs$：

$$ckabs(x)=\begin{cases}\left|x\right|& x\ne0\\\inf &x=0 \end{cases}$$

Part 2.2.1：$a_i$ 与 $b_i$ 配对：

$$f_i=f_{i-1}+ckabs(a_i-b_i)$$

Part 2.2.2：$a_i,a_{i-1}$ 与 $b_i,b_{i-1}$ 相互配对：

此时只用考虑 $(a_i,b_{i-1})$ 与 $(a_{i-1},b_i)$：

$$f_i=\min(f_i,f_{i-2}+ckabs(a_i-b_{i-1})+ckabs(a_{i-1}-b_i)) $$

Part 2.2.3：三对数配对：

借助贪心的思想，发现：对于 $a_i\footnotesize(i\in[2,n-1])$ 最优的搭配，是将它与 $b_{i-1}$、$b_i$ 或 $b_{i+1}$ 搭配时（即让 $a_{i-1},a_i,a_{i+1}$ 与 $b_{i-1},b_i,b_{i+1}$ 互相搭配，花费最小时就是最优搭配）。

改一下下标，有以下三种搭配：

1. $(a_i,b_{i-1}),(a_{i-1},b_{i-2}),(a_{i-2},b_i)$。
2. $(a_i,b_{i-2}),(a_{i-1},b_{i-1}),(a_{i-2},b_i)$。
3. $(a_i,b_{i-2}),(a_{i-1},b_i),(a_{i-2},b_{i-1})$。

得到状态转移方程：

$$f_i=\begin{cases}\min(f_i,f_{i-3}+ckabs(a_i-b_{i-1})+ckabs(a_{i-1},b_{i-2})+ckabs(a_{i-2},b_i))\\ \min(f_i,f_{i-3}+ckabs(a_i-b_{i-2})+ckabs(a_{i-1},b_{i-1})+ckabs(a_{i-2},b_i))\\ \min(f_i,f_{i-3}+ckabs(a_i-b_{i-2})+ckabs(a_{i-1},b_{i})+ckabs(a_{i-2},b_{i-1}))\end{cases}$$

Part 2.2.4：四对数配对

重复了，因为四对数可以被拆成两个两对数。

Part 2.3：初始化与边界状态

• 初始化：注意下标，对 $f_1$，$f_2$ 特殊关照：

$$f_1\gets ckabs(a_1-b_1)\\f_2\gets\min(f_1+ckabs(a_2-b_2),ckabs(a_1-b_2)+ckabs(a_2-b_1)) $$

• 边界状态：$i=n$。

Part 2.4：计算顺序与答案

• 计算顺序：$1\to n$。

• 答案：$f_n$。

Part 3：代码实现

注意开 long long。

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

#define int long long

#define T int
inline T read(){T x=0;char ch=getchar();while(ch<'0'||'9'<ch) ch=getchar();while('0'<=ch&&ch<='9') {x=(x<<3)+(x<<1)+(ch-'0');ch=getchar();}return x;}
void write(T x){if(x>9) write(x/10);putchar(x%10+'0');return ;}
#undef T

constexpr int inf=0x3f3f3f3f;

inline int min(int x,int y){return x<y?x:y;}

#define N 100005
#define pii pair<int,int>

int n;
int a[N],b[N],f[N];
signed main(){
	n=read();
	for(int i=1;i<=n;++i){
		a[i]=read(),b[i]=read();
	}
	
	sort(a+1,a+1+n),sort(b+1,b+1+n);
	
	auto ckabs=[](int x){return x==0?inf:x<0?-x:x;};
	
	f[1]=ckabs(a[1]-b[1]);
	f[2]=min(f[1]+ckabs(a[2]-b[2]),ckabs(a[1]-b[2])+ckabs(a[2]-b[1]));
	for(int i=3;i<=n;++i){
		f[i]=f[i-1]+ckabs(a[i]-b[i]);
		f[i]=min(f[i],f[i-2]+ckabs(a[i]-b[i-1])+ckabs(a[i-1]-b[i]));
		f[i]=min(f[i],f[i-3]+ckabs(a[i]-b[i-1])+ckabs(a[i-1]-b[i-2])+ckabs(a[i-2]-b[i]));
		f[i]=min(f[i],f[i-3]+ckabs(a[i]-b[i-2])+ckabs(a[i-1]-b[i-1])+ckabs(a[i-2]-b[i]));
		f[i]=min(f[i],f[i-3]+ckabs(a[i]-b[i-2])+ckabs(a[i-1]-b[i])+ckabs(a[i-2]-b[i-1]));
	}
	write(f[n]);
	return 0;
}

AC 记录（目前最优解）。