做得很郁悶的一道題。我開始已經想到是要用置換來算，但是提交后總是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 閱讀(393)
評論(1) 編輯 收藏 引用 所屬分類:
Algorithm - Combinatorics