做得很郁闷的一道题。我开始已经想到是要用置换来算，但是提交后总是WA。查代码查了N久也没有发现错误，感觉算法又没有问题。后来找到往年的解题报告，才发现我的基本思路没错，但是少考虑了一种情况。我之前认为最小代价等于一个置换内所有元素和 +（元素个数-2）* 置换内最小元素。但是解题报告说还有一种可能是这个置换内的最小元素和整个数列的最小元素交换，然后利用那个最小元素进行交换。这的确会产生更优的解，我原来怎么想不到呢！
题目代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10010;
struct Node
{
int v, id;
};
Node arr[N];
bool cmp(const Node &n1, const Node &n2)
{
return n1.v < n2.v;
}
int main()
{
int n, mine, cnt, pos, tol, ans, tmp, mini;
bool tag[N];
while (scanf("%d", &n) == 1)
{
mini = 0x3fffffff;
memset(tag, 0, sizeof(tag));
for (int i = 0; i < n; i++)
{
scanf("%d", &arr[i].v);
mini <?= arr[i].v;
arr[i].id = i;
}
sort(arr, arr + n, cmp);
ans = 0;
for (int i = 0; i < n; i++)
{
if (tag[i])
continue;
if (i == arr[i].id)
continue;
pos = i;
mine = arr[i].v;
cnt = 0;
tol = mine;
while (arr[pos].id != i)
{
cnt++;
pos = arr[pos].id;
tag[pos] = 1;
tol += arr[pos].v;
mine <?= arr[pos].v;
}
tmp = tol + (cnt - 1) * mine;
tmp <?= tol + mine + (cnt + 2) * mini;
ans += tmp;
}
printf("%d\n", ans);
}
return 0;
}
posted on 2009-04-17 09:05
sdfond 阅读(350)
评论(1) 编辑 收藏 引用 所属分类:
Algorithm - Combinatorics