洛谷 P2769 分析（别看）

科技起源‍‍‍‍‍‍‍‍‍‍‍‍

2026-07-24 18:04:38

发布于：北京

6阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：一个最小值

1.2 题目背景、允许、禁止与限制

背景：
有 $n$ 只猴子和 $m$ 棵树
允许：
第 $i$ 只猴子的位置为 $x_i$ ，第 $j$ 棵树的位置为 $y_j$ ，第 $i$ 只猴子上第 $j$ 棵树的代价为 $|x_i-y_j|$
限制：
最终上完树后确保每棵树上至少有 $1$ 只猴子（保证所有猴子上树）
求代价最小值

1.3 题目数据范围与猜测

$1 \le m \le n \le 5000 \longrightarrow O(n^2)$

1.4 一句话概括题意

有 $n$ 个位置互不相同的点和另外的 $m$ 个位置互不相同的点，求将 $n$ 个点移动到 $m$ 个点上，最终满足所有 $m$ 个点都要有至少 $n$ 个点中的 $1$ 个，求移动完毕后最小代价

2 题目破题推导

看到这题后，有一个关键点需要考虑到：全部上树的最小代价，一定是不会存在交叉匹配的

2.1 数学模型转化

现在我们把猴子和树看成两个一维数轴上的点：
猴子位置： $x_1<x_2<\cdots<x_{n-1}<x_n$
树的位置： $y_1<y_2<\cdots<y_{m-1}<y_n$

2.2 交叉配对定义

如果存在两只猴子 $a < b(x_a<x_b)$ ，两棵树 $c<d(y_c<y_d)$
则出现 $x_a\rightarrow y_d$ 或者 $x_b \rightarrow y_c$ 时就叫做交叉配对

2.3 证明

我们需要证明 $交叉配对价格 \ge 不交叉配对价格$

设实数满足 $(a\le b, c\le d)$ ，求证

$|a-d|+|b-c| \ge |a-c|+|b-d|$

令代价差

$\Delta=\big(|a-d|+|b-c|\big)-\big(|a-c|+|b-d|\big)$

情况1： $(a\le b\le c\le d)$

$\Delta=(d-a+c-b)-(c-a+d-b)=0$

情况2： $(c\le d\le a\le b)$

$\Delta=(a-d+b-c)-(a-c+b-d)=0$

情况3： $(a\le c\le b\le d)$

$\Delta=(d-a+b-c)-(c-a+d-b)=2(b-c)\ge 0$

情况4： $(a\le c\le d\le b)$

$\Delta=(d-a+b-c)-(c-a+b-d)=2(d-c)\ge 0$

情况5： $(c \le a \le b \le d)$

$\Delta = (d - a + b - c) - (a - c + d - b) = 2(b - a) \ge 0$

情况6： $(c \le a \le d \le b)$

$\Delta = (d - a + b - c) - (a - c + b - d) = 2(b - a) \ge 0$

综上恒有 $(\Delta\ge 0)$

$\boxed{|a-d|+|b-c| \ge |a-c|+|b-d|}$

3 模型匹配

格式为："关键词：...... $\longrightarrow$ $\huge{......}$ "

关键词：动态求取最小值，固定规律 $\longrightarrow$ $\huge{二维dp}$
但是这题开二维会MLE，因此滚动数组优化

4 最终代码（禁止抄袭，仅用于参考）

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

int n, m;
const int N = 5555;
int x[N];
int y[N];
int pre[N], now[N];

signed main(){

    cin >> n;
    for (int i = 1;i <= n;i++){
        cin >> x[i];
    }
    cin >> m;
    for (int i = 1;i <= m;i++){
        cin >> y[i];
    }
    sort(x + 1, x + 1 + n);
    sort(y + 1, y + 1 + m);
    memset(pre, 0x3f, sizeof(pre));
    pre[1] = abs(x[1] - y[1]);
    for (int i = 2;i <= n;i++){
        memset(now, 0x3f, sizeof(now));
        for (int j = 1;j <= m;j++){  
            now[j] = min(pre[j], pre[j - 1]) + abs(x[i] - y[j]);
        }
        memcpy(pre, now, sizeof(pre));
    }
    cout << pre[m];
        
    return 0;   
}