自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:54:10，当前版本为作者最后更新于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
*/