UVA 1016 - Silly Sort(置换分解+贪心)

本文主要是介绍UVA 1016 - Silly Sort(置换分解+贪心)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

UVA 1016 - Silly Sort

题目链接

题意：给定一个序列，数字都不同，每次可以交换两个数字，交换的代价为两数之和，要求出把这个序列变成递增最小代价

思路：利用置换的分解原理，可以把序列的每条循环单独考虑，对于每条循环而言，不断交换肯定每个数字至少会换到一次，再利用贪心的思想，如果每次拿循环中的最小值去置换，那么就是这个最小值会用长度-1次，而剩下的数字各一次，注意这里还有一种可能优的方法，就是先把整个序列中的最小值换到该循环中，等置换完再换出去，两种都考虑进来即可

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;const int N = 1005;int n, a[N], b[N], id[N], Min;int main() {int cas = 0;while (~scanf("%d", &n) && n) {Min = 1000;for (int i = 1; i <= n; i++) {scanf("%d", &a[i]);Min = min(Min, a[i]);b[i] = a[i];}sort(b + 1, b + n + 1);for (int i = 1; i <= n; i++)id[b[i]] = i;int ans = 0;for (int i = 1; i <= n; i++) {if (a[i]) {int cnt = 0;int sum = a[i];int now = id[a[i]];int tmp = a[i];a[i] = 0;while (a[now]) {cnt++;sum += a[now];tmp = min(tmp, a[now]);int save = now;now = id[a[now]];a[save] = 0;}ans += min(sum + tmp * cnt - tmp, sum + 2 * (tmp + Min) + Min * cnt - tmp);}}printf("Case %d: %d\n\n", ++cas, ans);}return 0;
}

这篇关于UVA 1016 - Silly Sort(置换分解+贪心)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---