CF797F Mice and Holes 题解

Description

有一天 Masha 回到家，发现有 $n$ 只老鼠在它公寓的走廊上，她大声呼叫，所以老鼠们都跑进了走廊的洞中。

这个走廊可以用一个数轴来表示，上面有 $n$ 只老鼠和 $m$ 个老鼠洞。第 $i$ 只老鼠有一个坐标 $x_i$ ，第 $j$ 个洞有一个坐标 $y_j$ 和容量 $c_j$ 。容量表示最多能容纳的老鼠数量。

找到让老鼠们全部都进洞的方式，使得所有老鼠运动距离总和最小。老鼠 $i$ 进入洞 $j$ 的运动距离 为 $|x_i − y_j|$。

无解输出 $-1$。

$n,m\leq 10^6$。

Solution

首先直接贪心就考虑每只老鼠选离它左边最近的或右边最近的钻，但是这样不是全局最优的。

考虑反悔贪心。

先把老鼠和洞放到一起按坐标从小到大排序，然后从前往后扫。设 $lstx_i$ 表示第 $i$ 只老鼠当前的最优答案，$lsty_i$ 表示第 $i$ 个洞当前的最优答案。然后用两个堆分别维护老鼠和洞的信息。

如果当前枚举到了第 $i$ 只老鼠，那么就要选一个洞匹配，设其为 $j$，那么匹配 $(i,j)$ 对答案的贡献就是 $(x_i-y_j)-lsty_j=x_i-(y_j+lsty_j)$，于是只要用洞堆维护最大的 $y_j+lsty_j$，然后把答案加上 $x_i-(y_j+lsty_j)$，同时 $lstx_i\leftarrow x_i-lsty_j$。由于当前老鼠还要反悔，所以把 $x_i+lstx_i$ 放到老鼠堆里面。

如果枚举到了第 $i$ 个洞是一样的，如果选了 $j$ 号老鼠，贡献就是 $y_i-(x_j+lstx_j)$，用老鼠堆维护最大的 $x_j+lstx_j$ 即可，然后把答案加上 $y_i-(x_j+lstx_j)$，同时 $lsty_i\leftarrow y_i-lstx_j$。

至于如何处理有一个坐标有很多个洞的问题，就每次只往堆里面放一个洞，如果这个匹配了就把匹配的放进去，然后如果还有洞就再选一个没匹配的洞放进去。

时间复杂度：$O((n+m)\log (n+m))$。

Code

#include <bits/stdc++.h>

#define int int64_t

const int kMaxN = 1e6 + 5, kInf = 1e16;

int n, m, mm;
int x[kMaxN];
std::pair<int, int> h[kMaxN], a[kMaxN];
std::priority_queue<int> qm;
std::priority_queue<std::pair<int, int>> qh;

void dickdreamer() {
  std::cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    std::cin >> x[i];
    a[++mm] = {x[i], 0};
  }
  int sumc = 0;
  for (int i = 1; i <= m; ++i) {
    std::cin >> h[i].first >> h[i].second;
    a[++mm] = {h[i].first, i};
    sumc += h[i].second;
  }
  if (sumc < n) {
    std::cout << "-1\n";
    return;
  }
  std::sort(a + 1, a + 1 + mm);
  int ans = 0;
  for (int i = 1; i <= mm; ++i) {
    if (!a[i].second) { // 老鼠
      int val = kInf;
      if (!qh.empty()) {
        auto [p, id] = qh.top();
        qh.pop();
        val = a[i].first - p;
        if (h[id].second) --h[id].second, qh.emplace(h[id].first, id);
      }
      ans += val;
      qm.emplace(a[i].first + val);
    } else { // 洞
      int val;
      while (!qm.empty() && h[a[i].second].second && (val = a[i].first - qm.top()) < 0) {
        --h[a[i].second].second;
        ans += val;
        qm.pop();
        qh.emplace(a[i].first + val, 0);
      }
      if (h[a[i].second].second) --h[a[i].second].second, qh.emplace(a[i].first, a[i].second);
    }
  }
  std::cout << ans << '\n';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}