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

· · 题解

由于懒惰进行了一个无耻的抄，希望各位谅解

法 1 (良心WA题人)

拆绝对值套路。考虑将相邻两条边的绝对值拆出来，有以下四种：

即对每种情况，考虑对于中间点 j，a,b​ 的符号。

显然合法图都能被这四种拼出来。考虑怎么拼才是合法：

显然由于正负个数相等，第二种和第四种个数要相等。

而第一种和第三种分别可以单独出现。若要同时出现，则至少有一个第二种和第四种（过渡）。\color{red}(*)

特判全一和全三。

显然可以从一开始全都是第一种或第三种（取最优），然后不断加入第二种和第四种（进行调整）边取最大值。可以用优先队列简单维护。

具体的：每次贪心的，同时加入当前最优的调整 (a_i+b_i-|a_i-b_i|) 和 (-a_j-b_j-|a_i-b_i|)。

若 i=j，则需要分别拿出调整值次大的 k,l，判断 (i,l) 和 (k,j) 应该同时调整哪一对。

优先队列调整，复杂度 O(n\log n)​。

关键代码参考：

for(int i=1;i<=n;i++)q1.emplace(a[i].fi+a[i].se-abs(a[i].fi-a[i].se),i),q2.emplace(-a[i].fi-a[i].se-abs(a[i].fi-a[i].se),i);
    while(q1.size()&&q2.size()){
        if(q1.top().se!=q2.top().se){
            res+=q1.top().first+q2.top().first;
        }else{
            int A=q1.top().first,B=q2.top().first;
            q1.pop();q2.pop();
            if(!q1.size())break;
            res+=max(A+q2.top().first,B+q1.top().first);
        }
        q1.pop();q2.pop();
        ans=max(ans,res);
    }

法 2 (TachiBK)

这个代码是最短的。

有个贪心：我们贪心强制对 a,b 定 n 个 +，n 个 -，使得组合出来的数最大。

此时只有少部分情况不合法，我们参考法 1 的 \color{red}(*)：

参考法 1 的分析，若此时在我贪心强制的定符号下，出现全一或全三，或者存在二四的单组（并且二四个数一致，判一个就行），那么方案一定合法。

否则一定一三均有，且无二四。考虑调整一组最优的符号即可，就把排序完的第 n 小调整为 +，第 n+1 小调整为 -。

如果第 n 小和第 n+1 小属于同一个数，那么调整又无效了。考虑调整 (n,n+2) 和 (n-1,n+1) 即可，看看哪个更优秀。

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

\bf{record}

法 3 (云斗题解+Alex_Wei)

不是很建议，有点小复杂

首先把答案设为 \sum a_i - \sum b_i， 然后考虑如果有一条边的 a_i < b_j， 我们就可以获得 2(b_j - a_i) 的收益。

考虑钦定一些边 (i, j) 被选中， 然后这些边不能连成环。 首先， 最优解一定可以被这样算到。 那么会不会有更优的解被算到呢， 发现我们如果给选定的这些位置随便钦定一个不成环的匹配（不管 a_i < b_j 的约束）， 那么当 a_i > b_j 的时候也会算入 2(b_j - a_i) < 0， 但实际贡献应该是 0。 于是我们不会算得更大。

于是只需要找两个集合 S, T 满足 |S| = |T|, S \neq T， 最大化 \sum_{i \in S} b_i - \sum_{j \in T} a_j。

将 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}​。

先这么选着，设两边选的对应的 c,d 的集合分别为 A,B，如果不符合条件，说明 A = B 且 0 < |A| < n，需要对方案进行调整。

对 \Delta |A| 分类讨论：

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

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

// code by Alex_Wei
#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
*/