CF797F F. Mice and Holes题解

F. Mice and Holes

题目翻译

​ 题目给我们n只老鼠在一个水平线上的坐标，这个水平线上还有m个洞，我们需要让每个老鼠都会到一个洞中，每个洞都有一个水平线上的坐标和容量，我们需要输出让所有老鼠到达洞的最小总移动距离，如果不可能让所有老鼠都到洞中则输出-1。

思路

​ 首先本题我们容易发现我们将洞和老鼠都排个序按坐标从小到大来考虑比较简单，我们容易得到一个O（n ^ 3)的dp解法，我们可以定义dp[i] [j] [k]表示考虑到第i支老鼠第j个洞，第j个洞进了k只老鼠的最小代价。根据贪心策略我们容易证明坐标小的老鼠进的洞一定小于等于坐标大的老鼠进的洞的坐标。但是O(n ^ 3)的时间复杂度我们无法接受。

​ 并且这个状态设计并不好优化，考虑转换状态，定义dp[i] [j]表示考虑到第i个洞进入了j只老鼠的最小代价。这个dp[i] [j] = Min(dp[i - 1] [j - k] + pre[i] [j] - pre[i] [j - k]) ，pre[i] [j]表示前j只老鼠进入第i个洞的代价。容易发现这个dp的j - k可以拎出来进行优化，于是每个转移实际上是查询一个区间长度为k的区间的最小值，这可以使用单调队列来左到O(1)的查询。于是我们使用单调队列优化这个dp即可。

​ 本题实际上还有O(n * lgn)的反悔贪心解法。具体的我们把洞和老鼠放到一起排序，当添加一个老鼠时我们会对其找最近的洞进行匹配，答案增加x - y。当洞进入时我们考虑对之前的老鼠进行反悔贪心，取消之前的贡献再加上新的贡献 -(x - y) + nowx - x，我们只要贪心的挑选y - 2 * x最大的即可。此外我们把这个贪心再次反悔，即让之后的老鼠进这个洞，我们撤销这次让之前老鼠进这个洞的贡献作为后续老鼠匹配这个洞的影响加入到维护洞的优先队列中。这样我们将老鼠的影响维护一个优先队列，将洞的影响维护一个优先队列，进行返回贪心就解决了本题。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
void solve(){
    int n, m;
    std::cin >> n >> m;
    std::vector<int> cur(n + 1, 0);
    for(int i = 1; i <= n; i++)
        std::cin >> cur[i];
    std::sort(cur.begin() + 1, cur.end());

    std::vector<std::pair<int, int>> pos(m + 1);
    for(int i = 1; i <= m; i++){
        std::cin >> pos[i].ff >> pos[i].ss;
    }
    std::sort(pos.begin() + 1, pos.end());

    std::vector dp(m + 1, std::vector<ll>(n + 1, 1e18));
    dp[0][0] = 0;
    for(int i = 1; i <= m; i++){
        std::deque<int> stk;
        stk.push_back(0);
        int c = pos[i].ss;
        dp[i][0] = 0;
        std::vector<ll> pre(n + 1, 0);
        for(int j = 1; j <= n; j++){
            pre[j] = pre[j - 1] + std::abs(cur[j] - pos[i].ff);
        }

        for(int j = 1; j <= n; j++){
            while(stk.size() && dp[i - 1][stk.back()] - pre[stk.back()] >= dp[i - 1][j] - pre[j]){
                stk.pop_back();
            }
            stk.push_back(j);
            while(stk.size() && stk.front() < j - c){
                stk.pop_front();
            }
            dp[i][j] = dp[i - 1][stk.front()] + pre[j] - pre[stk.front()];
        }
    }
    std::cout << (dp[m][n] >= 1e18 ? -1 : dp[m][n]) << endl;
}