有 $n$ 个互不相同的正整数 $a_1, a_2, \cdots, a_n$，你需要将它们按照从小到大的顺序排序。
你每次可以交换两个元素 $a_i$ 和 $a_j$ (不一定是相邻的)，这将花费你 $a_i + a_j$ 的代价。
你需要花费最小的代价将这些数排序，输出这个最小的代价。
第一行包含一个正整数 $n$ ($n \leq 10000$)，表示序列的长度。
接下来 $n$ 行，每行一个正整数 $a_i$ ($1 \leq a_i \leq 10^5$，$a_i$ 互不相同)，表示序列中的第 $i$ 项。
输出一行一个整数，表示最小的代价。
如果每次交换的代价为 $1$，那么就相当于询问最少交换次数。
而这个问题是比较平凡的，根据 [IOI2015]Sorting 中的结论，交换次数等于 $n$ 减去循环个数。
那么如果代价不是 $1$ 而是一般的整数，又该怎么处理呢？
我们还是一个循环一个循环地考虑，即先考虑在一个循环中，最少所需的交换次数。
首先，设有一个长度为 $n$ ($n \geq 2$) 的循环 $\left[ a_1 a_2 \cdots a_n \right]$。显然，交换次数至少是 $n - 1$，因此代价的和式中至少有 $2 n - 2$ 项。
又由于置换中每个元素均不在正确的位置，故它们至少参与一次交换，于是和式中每个 $a_i$ 至少出现一次。
结合上面两个红色性质可知，总代价的下界是 $a_1 + a_2 + \cdots + a_n + \left( n - 2 \right) \cdot \min \left\{ a_1, a_2, \cdots, a_n \right\}$。
另外，不妨设 $a_1 = \min \left\{ a_1, a_2, \cdots, a_n \right\}$，则通过交换 $\left( a_1, a_n \right), \left( a_1, a_{n-1} \right), \left( a_1, a_{n-2} \right), \cdots, \left( a_1, a_2 \right)$ 即可完成排序，而此时的代价就是刚才所说的 "下界" —— $\color {green} {a_1 + a_2 + \cdots + a_n + \left( n - 2 \right) a_1}$。
于是，我们只需要将每个循环内部的最小代价算出来，就可以得到解了。
但这样真的是正确的吗？我们这样做只是在保证交换次数最少情况下的答案，万一有某种方案虽然交换次数多，但是代价总和反而小，这又该怎么办呢？
这确实是存在的。考察一个长度为 $l$ ($l \geq 4$) 的循环，里面的元素都非常大 (大约为 $M$ 的数量级)，而外面有一个 $1$ 的元素。则考虑在循环内部处理，至少需要 $\left( 2 l - 2 \right) \cdot M$ 的代价。
反之，如果我们将 $1$ 加入这个循环，得到一个长度为 $l + 1$ 的循环，但是该循环中最小元素变为了 $1$，因此后续的代价只需要 $l \cdot M$，加上一开始换过去的 $M$，因此代价总和的数量级为 $\left( l + 1 \right) \cdot M$，当 $M \to + \infty$ 时，是远小于 $\left( 2 l - 2 \right) \cdot M$ 的。
因此，我们需要考虑一下第二种情况：即将全局最小值加入循环，然后再排序。设全局最小值为 $m_g$，则加入所需要的代价为 $m_g + a_1$，排序所需的代价为 $a_1 + a_2 + \cdots + a_n + n \cdot m_g$，故总代价为 $\color {green} {a_1 + a_2 + \cdots + a_n + \left( n + 1 \right) m_g + a_1}$。
于是，对每个循环，对这两种情况取个 $\min$ 再相加就是最终答案。
容易证明，最优解一定是 (对每个循环取) 这两个方法之一，没有其它的情况了。
总时间复杂度 $O(n)$。
#include <bits/stdc++.h>
typedef long long ll;
const int N = 100054;
int n;
int a[N], p[N], o[N];
bool used[N];
int main() {
int i, j, cnt; ll sum, ans = 0;
scanf("%d", &n);
for (i = 0; i < n; ++i) scanf("%d", a + i), o[i] = i;
std::sort(o, o + n, [] (const int x, const int y) {return a[x] < a[y];});
for (i = 0; i < n; ++i) p[o[i]] = i;
for (i = 0; i < n; ++i) if (!used[i]) {
sum = cnt = 0;
for (j = i; !used[j]; j = p[j]) used[j] = true, ++cnt, sum += a[o[j]];
ans += sum + std::min(a[o[i]] * (cnt - 2), a[o[i]] + a[*o] * (cnt + 1));
}
printf("%lld\n", ans);
return 0;
}
坑1：注意 $a_1, a_2, \cdots, a_n$ 并不一定是排列，因此一开始需要离散化一下。