CF797F Mice and Holes 题解

题目链接：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;
}

---

参考文献：

[1] https://yhx-12243.github.io/OI-transit/records/cf797F.html