题目描述

难度分:$2600$

输入$n(1 \leq n \leq 5000)$和$m(1 \leq m \leq 5000)$。

然后输入长为$n$的数组$a(-10^9 \leq a[i] \leq 10^9)$，表示在数轴上有$n$个一样的小球，第$i$ 个小球的位置是$a[i]$。

然后输入$m$行，每行两个数$p_i(-10^9 \leq p_i \leq 10^9)$和$c_i(1 \leq c_i \leq 5000)$，表示有$m$个洞，第$i$个洞的位置是$p_i$，能容纳$c_i$个小球。

把所有小球都移入洞中，移动距离之和的最小值是多少？如果无法满足，输出$-1$。

输入样例$1$

4 5
6 2 8 9
3 6
2 1
3 6
4 7
4 7

输出样例$1$

11

输入样例$2$

7 2
10 20 30 40 50 45 35
-1000000000 10
1000000000 1

输出样例$2$

7000000130

算法

划分型DP+单调队列优化

难得周五的茶可以做，比较明显的划分型DP，但是如果直接裸地套模板，时间复杂度会是$O(nm^2)$，在$5000$的量级下是肯定过不了的。首先有个贪心的思路，每个洞解决的老鼠，一定是连续的一段，所有洞解决的老鼠区间拼成整体，因此可以先将洞和老鼠按照位置排序。

状态定义

$dp[i][j]$表示前$j$只老鼠（原题不是小球，是老鼠进洞）进入前$i$个洞所需要移动的最小距离之和，在这个定义下答案就应该是$dp[m][n]$。

状态转移

$base$ $case$：$dp[0][0]=0$，表示没有老鼠就无需移动。

一般情况：从前往后考虑洞$i \in [1,m]$，然后枚举前$i$个洞需要收容的老鼠数量$j$。根据闫氏DP分析法，对于$dp[i][j]$我们需要找到最后一个不同点，即枚举最后一个洞$i$要容纳多少只老鼠。枚举前$i-1$个洞的老鼠数量$k$，则有状态转移方程$dp[i][j]=s[j]+min_{k \in [j-hole[i].c,precapacity]}(dp[i-1][k]-s[k])$，其中$precapacity$表示前$i-1$个洞的总容量，$hole[i].c$表示第$i$个洞的容量。$s$是个前缀和数组，$s[j]$表示前$j$只老鼠都进第$i$个洞的距离之和，每次遍历$j \in [0,n]$之前，可以先$O(n)$求一遍这个前缀和数组，用于后续的状态转移。

最多的情况下前$i-1$个洞会满员，最少的情况下最后一个洞是满的，其余的$j-hole[i].c$只老鼠在前$i-1$个洞（$k$的范围可能还会存在一些细节问题，这里主要给出考虑上下界的思路，具体细节在代码中实现）。因此最后一个洞中，老鼠的数量就应该是$s[j]-s[k]$。

优化

发现状态转移里存在求区间最小值的操作，要高效求动态区间最小值其实有很多方法，但是本题时间卡得比较紧，并且$n,m \leq 5000$的范围还是比较大的，所以不能直接无脑上线段树。而线性方法求区间最值那就比较经典了，由于遍历$j$时$s[j]$是确定的，可以用单调队列来维护$dp[i-1][k]-s[k]$最小值对应的索引$k$，这样就能把整个DP过程的时间复杂度控制在$O(mn)$。

复杂度分析

时间复杂度

在DP的过程中双重循环遍历$i \in [1,m]$和$j \in [1,n]$，单调队列优化过的状态转移是$O(1)$的，因此整个算法的时间复杂度为$O(mn)$。

空间复杂度

前缀和数组$s$的空间为$O(m)$，单调队列在最差情况下会进入$O(n)$级别的索引，动态规划的状态数量为$O(mn)$。因此，整个算法的空间瓶颈在于DP矩阵$dp$，额外空间复杂度为$O(mn)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 5010;
const LL INF = 1e18;

struct Hole {
    int pos, c;
    bool operator<(const Hole other) {
        return pos < other.pos;
    }
} hole[N];

int n, m, x[N];
LL dp[N][N], s[N];

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &x[i]);
    }
    sort(x + 1, x + n + 1);
    for(int i = 1; i <= m; i++) {
        scanf("%d%d", &hole[i].pos, &hole[i].c);
    }
    sort(hole + 1, hole + m + 1);
    for(int i = 0; i <= m; i++) {
        for(int j = 0; j <= n; j++) {
            dp[i][j] = INF;
        }
    }
    dp[0][0] = 0;
    // dp[i][j]前j只老鼠进入前i个洞的最小移动距离
    LL pre_capacity = 0;
    for(int i = 1; i <= m; i++) {
        // 计算前j只老鼠都进入第i个洞的移动距离
        pre_capacity += hole[i].c;
        for(int j = 1; j <= n; j++) {
            s[j] = s[j - 1] + abs(x[j] - hole[i].pos);
        }
        deque<int> q;
        for(int j = 0; j <= pre_capacity && j <= n; j++) {
            // 枚举前i-1个洞进的老鼠
            while(!q.empty() && q.front() < j - hole[i].c) {
                q.pop_front();
            }
            while(!q.empty() && dp[i - 1][q.back()] - s[q.back()] >= dp[i - 1][j] - s[j]) {
                q.pop_back(); 
            }
            q.push_back(j);
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][q.front()] + s[j] - s[q.front()]);
        }
    }
    printf("%lld\n", dp[m][n] > INF/2? -1: dp[m][n]);
    return 0;
}