嘘~ 正在从服务器偷取页面 . . .

CF797F Mice and Holes 题解

发布日期: 2023-03-28

更新日期: 2023-03-28

文章字数: 753

CF797F Mice and Holes 题解

题意：
走廊可以看作是一个一个数轴，上面有 $n$ 个老鼠和 $m$ 个洞，第 $i$ 个老鼠的坐标是 $x_i$ ，第 $j$ 个洞的坐标是 $p_j$ ，可以容纳 $c_j$ 个老鼠。

如果第 $i$ 个老鼠去洞 $j$ ，当然，它需要走 $\left|x_i-p_j\right|$ 的距离，求所有老鼠都到达某个洞最小距离和。

输入格式：

第一行包含两个正整数 $n, m(n, m \leq 5000)$, 分别表示老鼠和洞的数量。

第二行包含 $n$ 个整数 $x_1, x_2, \cdots, x_n\left(-10^9 \leq x_i \leq 10^9\right), x_i$ 表示第 $i$ 个老鼠的坐标。

接下来的 $m$ 行中, 第 $j$ 行有两个正整数 $p_j, c_j\left(-10^9 \leq p_j \leq 10^9, 1 \leq c_j \leq 5000\right), p_j, c_j$ 分别表示第 $j$ 个洞的坐标和容量。

输出格式：

输入一行一个整数，代表最小距离和，如果不能使所有老鼠都到达洞，输出 -1 。

先把老鼠和洞分别按位置排个序，然后对 $c$ 做个前缀和 $C$ 。

设 $f_{i,j}$ 表示前 $i$ 个洞，前 $j$ 只老鼠均跑进洞中的最小距离和，当 $j > C_i$ 时记 $f_{i,j} = +\infty$ 。则

$f_{i, j}=\min _{j-c_i \leq k \leq j}\left\{f_{i-1, k}+\sum_{l=k+1}^j\left|x_l-p_i\right|\right\}$

记 $s_{i,j} = \sum_{l = 1}^{j} |x_l - p_i|$ ，即前 $j$ 个老鼠进第 $i$ 个洞的距离和，则

$f_{i, j}=\min _{j-c_i \leq k \leq j}\left\{f_{i-1, k}+y_{i, j}-y_{i, k}\right\}=\min _{j-c_i \leq k \leq j}\left\{f_{i-1, k}-y_{i, k}\right\}+y_{i, j}$

考虑单调队列优化，最后答案即 $f_{m,n}$ 。

时间复杂度 $\mathcal{O}(nm)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(5e3 + 15))
#define p first
#define c second

int n,m,st,en,x[N],s[N],q[N],f[N][N];
pair<int,int> h[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m; memset(f, 0x3f, sizeof(f)); f[0][0] = 0;
    for(int i = 1; i <= n; i++) cin >> x[i];
    for(int i = 1; i <= m; i++) cin >> h[i].p >> h[i].c;
    sort(x + 1, x + 1 + n); sort(h + 1, h + 1 + m);
    for(int i = 1; i <= m; i++) { h[i].c += h[i - 1].c; f[i][0] = 0; }
    for(int i = 1,k; i <= m; i++)
    {
        for(int j = 1; j <= n; j++) { s[j] = s[j - 1] + abs(x[j] - h[i].p); }
        q[st = en = 0] = 0; q[++en] = 0;
        for(int j = 1; j <= h[i].c && j <= n; j++)
        {
            k = j - h[i].c + h[i - 1].c;
            for(; st < en && q[st + 1] < k; ++st);
            for(; st < en && f[i - 1][q[en]] - s[q[en]] >= f[i - 1][j] - s[j]; --en);
            q[++en] = j; k = q[st + 1]; f[i][j] = f[i - 1][k] - s[k] + s[j];
        }
    }
    cout << (f[m][n] < INF ? f[m][n] : -1) << '\n';
    return 0;
}