专栏文章

题解：P10747 [SEERC 2020] Neo-Robin Hood

wweilycoder东临碣石
P10747题解参与者 4已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@min3nivl
此快照首次捕获于
2025/12/01 20:02
3 个月前
此快照最后确认于
2025/12/01 20:02
3 个月前
查看原文
我承认一些观察可能有紫，因为我的确做的时候都没注意到。
但是反贪可以直接艹过去。
首先发现盗窃人数肯定是有单调性的，因此先套一个二分答案。
现在只需要对于当前二分到的 kk，判断能否选择 kk 个 mim_i 和 kk 个 pjp_j，使得收益 S=(∑mi)−(∑pj)⩾0S=\left(\sum m_i\right)-\left(\sum p_j\right)\geqslant 0。
将人分成 33 组，AA 组每人贡献一个 mim_i 的收益；BB 组每人贡献一个 −pj-p_j 的收益；CC 组不做贡献。我们需要最大化收益 SS。
考虑直接反悔贪心，首先随便给每个人分组，然后用 66 个优先队列维护：
  • 将 AA 集合中的一个人拿出来放到 BB 集合的收益（HABH_{AB}）；
  • 将 AA 集合中的一个人拿出来放到 CC 集合的收益（HACH_{AC}）；
  • 将 BB 集合中的一个人拿出来放到 AA 集合的收益（HBAH_{BA}）；
  • 将 BB 集合中的一个人拿出来放到 CC 集合的收益（HBCH_{BC}）；
  • 将 CC 集合中的一个人拿出来放到 AA 集合的收益（HCAH_{CA}）；
  • 将 CC 集合中的一个人拿出来放到 BB 集合的收益（HCBH_{CB}）。
由于优先队列不支持直接删除，需要同时维护人的下标，方便进行懒删除。
总共只有 66 种变换：
  • 交换 A,BA,B 集合中的某个数；
  • 交换 B,CB,C 集合中的某个数；
  • 交换 C,AC,A 集合中的某个数；
  • 将 A,B,CA,B,C 集合中各取一个数轮换；
  • 将 C,B,AC,B,A 集合中各取一个数轮换；
  • 啥也不做。
每次从六种方案中选择一个收益最大且为正的执行交换即可，直到无法操作，显然每个元素不会被操作超过 22 次，因此 check 的复杂度为 O(nlog⁡n)\mathcal O\left(n\log n\right)。
当然操作到 SS 大于等于 00 就可以直接停止了。
总复杂度 O(nlog⁡2n)\mathcal O\left(n\log^2 n\right)。
CodeCPP
#include <bits/stdc++.h>
using namespace std;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin.exceptions(cin.failbit | cin.badbit);
  size_t n;
  cin >> n;
  vector<pair<int64_t, int64_t>> items(n);
  for (size_t i = 0; i < n; ++i)
    cin >> items[i].first;
  for (size_t i = 0; i < n; ++i)
    cin >> items[i].second;
  auto check = [&](size_t mid) {
    if (mid * 2 > n)
      return false;
    if (mid == 0)
      return true;
    vector<bool> A(n, false), B(n, false), C(n, false);
    using MaxHeap = priority_queue<pair<int64_t, size_t>>;
    MaxHeap heapAB, heapBC, heapCA, heapBA, heapAC, heapCB;
    int64_t total = 0;

    auto pushA = [&](size_t i) {
      heapAC.emplace(-(items[i].first), i);
      heapAB.emplace(-(items[i].first + items[i].second), i);
    };
    auto pushB = [&](size_t i) {
      heapBC.emplace(+(items[i].second), i);
      heapBA.emplace(+(items[i].first + items[i].second), i);
    };
    auto pushC = [&](size_t i) {
      heapCA.emplace(+(items[i].first), i);
      heapCB.emplace(-(items[i].second), i);
    };

    for (size_t i = 0; i < mid; ++i)
      total += items[i].first, A[i] = true, pushA(i);
    for (size_t i = mid; i < 2 * mid; ++i)
      total -= items[i].second, B[i] = true, pushB(i);
    for (size_t i = mid * 2; i < n; ++i)
      C[i] = true, pushC(i);

    while (total < 0) {
      while (!heapAB.empty() && !A[heapAB.top().second])
        heapAB.pop();
      while (!heapAC.empty() && !A[heapAC.top().second])
        heapAC.pop();
      while (!heapBA.empty() && !B[heapBA.top().second])
        heapBA.pop();
      while (!heapBC.empty() && !B[heapBC.top().second])
        heapBC.pop();
      while (!heapCA.empty() && !C[heapCA.top().second])
        heapCA.pop();
      while (!heapCB.empty() && !C[heapCB.top().second])
        heapCB.pop();
      int64_t swapAB = numeric_limits<int64_t>::min();
      int64_t swapAC = numeric_limits<int64_t>::min();
      int64_t swapBC = numeric_limits<int64_t>::min();
      int64_t cirABC = numeric_limits<int64_t>::min();
      int64_t cirACB = numeric_limits<int64_t>::min();
      if (!heapAB.empty() && !heapBA.empty())
        swapAB = heapAB.top().first + heapBA.top().first;
      if (!heapAC.empty() && !heapCA.empty())
        swapAC = heapAC.top().first + heapCA.top().first;
      if (!heapBC.empty() && !heapCB.empty())
        swapBC = heapBC.top().first + heapCB.top().first;
      if (!heapAB.empty() && !heapBC.empty() && !heapCA.empty())
        cirABC = heapAB.top().first + heapBC.top().first + heapCA.top().first;
      if (!heapAC.empty() && !heapCB.empty() && !heapBA.empty())
        cirACB = heapAC.top().first + heapCB.top().first + heapBA.top().first;
      if (swapAB <= 0 && swapAC <= 0 && swapBC <= 0 && cirABC <= 0 && cirACB <= 0)
        break;
      int64_t max_gain = max({swapAB, swapAC, swapBC, cirABC, cirACB});
      if (max_gain == cirABC) {
        total += cirABC;
        size_t i = heapAB.top().second;
        size_t j = heapBC.top().second;
        size_t k = heapCA.top().second;
        A[i] = false, B[i] = true;
        B[j] = false, C[j] = true;
        C[k] = false, A[k] = true;
        heapAB.pop(), heapBC.pop(), heapCA.pop();
        pushB(i), pushC(j), pushA(k);
      } else if (max_gain == cirACB) {
        total += cirACB;
        size_t i = heapAC.top().second;
        size_t j = heapCB.top().second;
        size_t k = heapBA.top().second;
        A[i] = false, C[i] = true;
        C[j] = false, B[j] = true;
        B[k] = false, A[k] = true;
        heapAC.pop(), heapCB.pop(), heapBA.pop();
        pushC(i), pushB(j), pushA(k);
      } else if (max_gain == swapAB) {
        total += swapAB;
        size_t i = heapAB.top().second;
        size_t j = heapBA.top().second;
        A[i] = false, B[i] = true;
        B[j] = false, A[j] = true;
        heapAB.pop(), heapBA.pop();
        pushB(i), pushA(j);
      } else if (max_gain == swapAC) {
        total += swapAC;
        size_t i = heapAC.top().second;
        size_t j = heapCA.top().second;
        A[i] = false, C[i] = true;
        C[j] = false, A[j] = true;
        heapAC.pop(), heapCA.pop();
        pushC(i), pushA(j);
      } else if (max_gain == swapBC) {
        total += swapBC;
        size_t i = heapBC.top().second;
        size_t j = heapCB.top().second;
        B[i] = false, C[i] = true;
        C[j] = false, B[j] = true;
        heapBC.pop(), heapCB.pop();
        pushC(i), pushB(j);
      } else {
        break;
      }
    }
    return total >= 0;
  };
  int64_t left = 0, right = n / 2;
  while (left < right) {
    int64_t mid = left + (right - left + 1) / 2;
    if (check(mid))
      left = mid;
    else
      right = mid - 1;
  }
  cout << left << '\n';
  return 0;
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...