考虑将 \(\min(a_i,b_j)\) 转化为任意选择 \(a_i,b_j\)，因为多出来的不合法状态答案一定不会变小。
注意到一个合法的行走方案对于 \(a_i,b_j\) 的选择只有如下两种情况之一：
- 全选 \(a\) 或者全选 \(b\)。
- 存在一个点 \(a,b\) 全选。
1 证明显然，2 证明就是考虑如果不满足就会出现不等式环。
将所有 \(a,b\) 丢到长为 \(2n\) 的数据 \(c\)，升序排序，先检验 \(\sum_{i=1}^{n}c_i\) 是否合法，如果不合法就考虑将 \(c_n\) 换成 \(c_{n+1}\)，再考虑是否合法，若还不合法说明 \(c_n,c_{n+1}\) 是一个点的 \(a,b\)，此时将 \(c_{n-1}\) 换成 \(c_n\) 或者 \(c_{n+1}\) 换成 \(c_{n+2}\) 都必然满足上述条件 2，取最小值即可。
Code：
/*
========= Plozia =========
Author:Plozia
Problem:
Date:2022/9/25
========= Plozia =========
*/
#include <bits/stdc++.h>
typedef long long LL;
const int MAXN = 1e5 + 5;
int n, book[MAXN];
struct node { int Num, id, opt; bool operator <(const node &fir)const { return (Num < fir.Num); } } a[MAXN << 1];
int Read()
{
int sum = 0, fh = 1; char ch = getchar();
for (; ch < '0' || ch > '9'; ch = getchar()) fh -= (ch == '-') << 1;
for (; ch >= '0' && ch <= '9'; ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch ^ 48);
return sum * fh;
}
int main()
{
n = Read();
for (int i = 1; i <= n; ++i)
{
a[i * 2 - 1].Num = Read(); a[i * 2 - 1].id = i; a[i * 2 - 1].opt = 1;
a[i * 2].Num = Read(); a[i * 2].id = i; a[i * 2].opt = 2;
}
std::sort(a + 1, a + 2 * n + 1);
int sum = 0, fir = 0, sec = 0; LL ans = 0;
for (int i = 1; i <= n; ++i) { sum += (book[a[i].id] == 0); ++book[a[i].id]; if (a[i].opt == 1) ++fir; else ++sec; ans += 1ll * a[i].Num;}
if (fir == n || sec == n || sum < n) { printf("%lld\n", ans); return 0; }
--book[a[n].id]; if (a[n].opt == 1) --fir; else --sec; sum -= (book[a[n].id] == 0); ans -= a[n].Num;
++book[a[n + 1].id]; if (a[n + 1].opt == 1) ++fir; else ++sec; sum += (book[a[n + 1].id] == 1); ans += a[n + 1].Num;
if (fir == n || sec == n || sum < n) { printf("%lld\n", ans); return 0; }
printf("%lld\n", std::min(ans - a[n + 1].Num + a[n + 2].Num, ans - a[n - 1].Num + a[n].Num)); return 0;
}