I、How to sort

https://ac.nowcoder.com/acm/contest/554/I

1、考虑数字成环来移动肯定是最优的。

2、如果发现了一个环，假设环上有k个数字，那么使用k个数字中最小的数字来移动其他数字应该是较优的。

此时这个环的贡献为 环上最小值*(k-1)+环上除最小值之外的其他值。

3、但是，在第二点的基础上，一直83.3%，然后发现了，第二点并不一定是最优，你可以考虑使用环外的最小数来移动这个环上的数字，虽然多移动了一次，但是贡献有可能会更小。

此时贡献为 环上的所有值+环上的最小值+整个序列的最小值*(n+1)

4、第二点和第三点取一下min，就可以了，记得要先hash一下。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int a[10005], t[10005], cnt;
bool book[10005];
int has(int k)
{
	return lower_bound(t, t + cnt, k) - t;
}
int main()
{
	int n, MIN = 1e9;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
		t[i] = a[i];
		MIN = min(MIN, a[i]);
	}
	sort(t + 1, t + 1 + n);
	cnt = unique(t + 1, t + n + 1) - t - 1;
	for (int i = 1; i <= n; i++)
		a[i] = lower_bound(t + 1, t + 1 + cnt, a[i]) - t;
	ll ans = 0;
	for (int i = 1; i <= n; i++)
	{
		if (book[i] == false)
		{
			book[i] = true;
			ll sum = 0, minn = t[a[i]];
			int cnt = 1;
			sum += t[a[i]];
			for (int j = a[i]; j != i; j = a[j])
			{
				book[j] = true;
				sum += t[a[j]];
				minn = min(minn, 1LL * t[a[j]]);
				cnt++;
			}
			if (cnt != 1)
				ans += min(sum + minn * (cnt - 2), minn + sum + (cnt + 1) * MIN);
		}
	}
	printf("%lld", ans);
}