原题链接
1 题目
1.1 题目所需求出内容
对于本题，最终要求：一个最小值
1.2 题目背景、允许、禁止与限制
背景：
有 nnn 只猴子和 mmm 棵树
允许：
第 iii 只猴子的位置为 xix_ixi ，第 jjj 棵树的位置为 yjy_jyj ，第 iii 只猴子上第 jjj 棵树的代价为 ∣xi−yj∣|x_i-y_j|∣xi −yj ∣
限制：
最终上完树后确保每棵树上至少有 111 只猴子（保证所有猴子上树）
求代价最小值
1.3 题目数据范围与猜测
1≤m≤n≤5000⟶O(n2)1 \le m \le n \le 5000 \longrightarrow O(n^2)1≤m≤n≤5000⟶O(n2)
1.4 一句话概括题意
有 nnn 个位置互不相同的点和另外的 mmm 个位置互不相同的点，求将 nnn 个点移动到 mmm 个点上，最终满足所有 mmm 个点都要有至少 nnn 个点中的 111 个，求移动完毕后最小代价
2 题目破题推导
看到这题后，有一个关键点需要考虑到：全部上树的最小代价，一定是不会存在交叉匹配的
2.1 数学模型转化
现在我们把猴子和树看成两个一维数轴上的点：
猴子位置：x1<x2<⋯<xn−1<xnx_1<x_2<\cdots<x_{n-1}<x_nx1 <x2 <⋯<xn−1 <xn
树的位置：y1<y2<⋯<ym−1<yny_1<y_2<\cdots<y_{m-1}<y_ny1 <y2 <⋯<ym−1 <yn
2.2 交叉配对定义
如果存在两只猴子 a<b(xa<xb)a < b(x_a<x_b)a<b(xa <xb )，两棵树 c<d(yc<yd)c<d(y_c<y_d)c<d(yc <yd )
则出现 xa→ydx_a\rightarrow y_dxa →yd 或者 xb→ycx_b \rightarrow y_cxb →yc 时就叫做交叉配对
2.3 证明
我们需要证明 交叉配对价格≥不交叉配对价格交叉配对价格 \ge 不交叉配对价格交叉配对价格≥不交叉配对价格
设实数满足 (a≤b,c≤d)(a\le b, c\le d)(a≤b,c≤d)，求证
∣a−d∣+∣b−c∣≥∣a−c∣+∣b−d∣|a-d|+|b-c| \ge |a-c|+|b-d| ∣a−d∣+∣b−c∣≥∣a−c∣+∣b−d∣
令代价差
Δ=(∣a−d∣+∣b−c∣)−(∣a−c∣+∣b−d∣)\Delta=\big(|a-d|+|b-c|\big)-\big(|a-c|+|b-d|\big) Δ=(∣a−d∣+∣b−c∣)−(∣a−c∣+∣b−d∣)
情况1：(a≤b≤c≤d)(a\le b\le c\le d)(a≤b≤c≤d)
Δ=(d−a+c−b)−(c−a+d−b)=0\Delta=(d-a+c-b)-(c-a+d-b)=0 Δ=(d−a+c−b)−(c−a+d−b)=0
情况2：(c≤d≤a≤b)(c\le d\le a\le b)(c≤d≤a≤b)
Δ=(a−d+b−c)−(a−c+b−d)=0\Delta=(a-d+b-c)-(a-c+b-d)=0 Δ=(a−d+b−c)−(a−c+b−d)=0
情况3：(a≤c≤b≤d)(a\le c\le b\le d)(a≤c≤b≤d)
Δ=(d−a+b−c)−(c−a+d−b)=2(b−c)≥0\Delta=(d-a+b-c)-(c-a+d-b)=2(b-c)\ge 0 Δ=(d−a+b−c)−(c−a+d−b)=2(b−c)≥0
情况4：(a≤c≤d≤b)(a\le c\le d\le b)(a≤c≤d≤b)
Δ=(d−a+b−c)−(c−a+b−d)=2(d−c)≥0\Delta=(d-a+b-c)-(c-a+b-d)=2(d-c)\ge 0 Δ=(d−a+b−c)−(c−a+b−d)=2(d−c)≥0
情况5： (c≤a≤b≤d)(c \le a \le b \le d)(c≤a≤b≤d)
Δ=(d−a+b−c)−(a−c+d−b)=2(b−a)≥0\Delta = (d - a + b - c) - (a - c + d - b) = 2(b - a) \ge 0 Δ=(d−a+b−c)−(a−c+d−b)=2(b−a)≥0
情况6：(c≤a≤d≤b)(c \le a \le d \le b)(c≤a≤d≤b)
Δ=(d−a+b−c)−(a−c+b−d)=2(b−a)≥0\Delta = (d - a + b - c) - (a - c + b - d) = 2(b - a) \ge 0 Δ=(d−a+b−c)−(a−c+b−d)=2(b−a)≥0
综上恒有 (Δ≥0)(\Delta\ge 0)(Δ≥0)
∣a−d∣+∣b−c∣≥∣a−c∣+∣b−d∣\boxed{|a-d|+|b-c| \ge |a-c|+|b-d|} ∣a−d∣+∣b−c∣≥∣a−c∣+∣b−d∣
3 模型匹配
> 格式为："关键词：...... ⟶\longrightarrow⟶ ......\huge{......}......"
关键词：动态求取最小值，固定规律 ⟶\longrightarrow⟶ 二维dp\huge{二维dp}二维dp
但是这题开二维会MLE，因此滚动数组优化
4 最终代码（禁止抄袭，仅用于参考）
