P10046 [CCPC 2023 北京市赛] 哈密顿

Alex_Wei · 2024-01-16 23:34:17 · 题解

*P10046 [CCPC 2023 北京市赛] 哈密顿

问题等价于每个 a_i 匹配一个 b_j，不同的 a_i 匹配不同的 b_j，且匹配关系形成一个大环。即若 a_i 匹配 b_j 则连边 i\to j，图是一个环。

绝对值太烦人了，先去掉，则答案为 \sum a_i - \sum b_j。

考虑到每个 a_i < b_j 会让答案增加 2(b_j - a_i)，则问题等价于选择相同数量的 a_i 和 b_j，让选中的 a_i 只会匹配选中的 b_j，匹配的 a_i 和 b_j 满足 a_i < b_j，并且除非全选，否则匹配关系不能成环。如果目前的匹配关系不成环，那么容易构造出补充匹配使得图是一个大环的情况。

• 如果选出的匹配（钦定 a_i < b_j）存在 a_i > b_j 的情况，其贡献为 b_j - a_i，只会将答案算小。
• 如果补充的匹配（钦定 a_i > b_j）存在 a_i < b_j 的情况，其贡献为 a_i - b_j，只会将答案算小。
• 要让选出的匹配不成环，只需让选出的 a_i 下标集合 A 和 b_j 下标集合 B 不完全相同。每次选 A\backslash B 的某个 i，让它匹配 A\cap B 的某个 j，然后从 A 删去 i，从 B 删去 j，则 A\backslash B 大小不变且一定不会成环。假设 u\to v 成环，那么 v\in B 且 v 之前作为某个 i 出现，即当时 v\in A，则当时 v\in A\cap B，和 v\in A\backslash B 矛盾。当 A\cap B = \varnothing 时随便匹配就行。因为初始 A\backslash B \neq \varnothing，所以构造可行。

因此，我们的目标是在选中的两组下标集合不完全相同的限制下，最大化选出的 \sum b_j - \sum a_i。

将 a_i 和 b_j 从小到大排序，设它们原来的下标为 c_i 和 d_j。显然，如果没有限制，则一定会选 a_{1\sim k} 和 b_{n - k + 1\sim n}，满足 a_k < b_{n - k + 1} 但 a_{k + 1} > b_{n - k}。先这么选着，如果不符合条件，说明 A = B 且 0 < |A| < n，需要对方案进行调整。

对 \Delta |A| 分类讨论：

• 若 \Delta |A| = -1，则
  • 若 c_k \neq d_{n - k + 1} 或者 |A| = 1，则将 c_k 和 d_{n - k + 1} 分别从 A 和 B 中删去。
  • 否则删去 c_k 和 d_{n - k + 2}，或 c_{k - 1} 和 d_{n - k + 1}。
• 若 \Delta |A| = 0，则将 c_k 和 d_{n - k + 1} 删去，换成 c_k 和 d_{n - k}，或 c_{k + 1} 和 d_{n - k + 1}。
• 若 \Delta |A| = 1，则
  • 若 c_{k + 1}\neq d_{n - k} 或 |A| = n - 1，则加入 c_{k + 1} 和 d_{n - k}。
  • 否则加入 c_{k + 1} 和 d_{n - k - 1}，或 c_{k + 2} 和 d_{n - k}。

正确性证明分两步，一步是证明给出的方案是在固定 \Delta |A| 之后最优的，另一步是证明其它 \Delta |A| 一定不优于 \Delta |A| = \pm 1 的情况。具体细节留给读者自行补充。

时间复杂度为除排序外线性。

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdi = pair<double, int>;
using pdd = pair<double, double>;
using ull = unsigned long long;
using LL = __int128_t;

#define ppc(x) __builtin_popcount(x)
#define clz(x) __builtin_clz(x)

bool Mbe;

// ---------- templates above ----------

constexpr int N = 1e5 + 5;

int n;
struct dat {
  int val, id;
  bool operator < (const dat &z) const {
    return val < z.val;
  }
} a[N], b[N];
void solve() {
  cin >> n;
  for(int i = 1; i <= n; i++) {
    cin >> a[i].val >> b[i].val;
    a[i].id = b[i].id = i;
  }
  sort(a + 1, a + n + 1);
  sort(b + 1, b + n + 1);
  int l = 0, r = n + 1;
  map<int, int> mp;
  ll ans = 0;
  while(l < n) {
    if(a[l + 1].val > b[r - 1].val) break;
    mp[a[++l].id]++, mp[b[--r].id]--;
    ans += b[r].val - a[l].val;
  }
  bool ok = 0;
  for(pii it : mp) ok |= it.second > 0;
  if(!ok && l < n && l) {
    ll res = -1e18;
    auto f = [&](int l, int r) {
      return ll(b[r].val - a[l].val);
    };
    if(a[l].id != b[r].id || l == 1) res = max(res, -f(l, r));
    else res = max(res, max(-f(l, r + 1), -f(l - 1, r)));
    res = max(res, max(f(l, r - 1), f(l + 1, r)) - f(l, r));
    if(a[l + 1].id != b[r + 1].id || l == n - 1) res = max(res, f(l + 1, r - 1));
    else res = max(res, max(f(l + 2, r - 1), f(l + 1, r - 2)));
    ans += res;
  }
  ans *= 2;
  for(int i = 1; i <= n; i++) ans += a[i].val - b[i].val;
  cout << ans << endl;
}

bool Med;
signed main() {
  fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
  // ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  #ifdef ALEX_WEI
    FILE* IN = freopen("1.in", "r", stdin);
    FILE* OUT = freopen("1.out", "w", stdout);
  #endif
  int T = 1;
  while(T--) solve();
  fprintf(stderr, "%.3lf ms\n", 1e3 * clock() / CLOCKS_PER_SEC);
  return 0;
}

/*
g++ a.cpp -o a -std=c++14 -O2 -DALEX_WEI
*/