做得很郁悶的一道題。我開始已經(jīng)想到是要用置換來算，但是提交后總是WA。查代碼查了N久也沒有發(fā)現(xiàn)錯誤，感覺算法又沒有問題。后來找到往年的解題報告，才發(fā)現(xiàn)我的基本思路沒錯，但是少考慮了一種情況。我之前認(rèn)為最小代價等于一個置換內(nèi)所有元素和 +（元素個數(shù)-2）* 置換內(nèi)最小元素。但是解題報告說還有一種可能是這個置換內(nèi)的最小元素和整個數(shù)列的最小元素交換，然后利用那個最小元素進(jìn)行交換。這的確會產(chǎn)生更優(yōu)的解，我原來怎么想不到呢！
題目代碼：
#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 閱讀(401)
評論(1) 編輯 收藏 引用 所屬分類:
Algorithm - Combinatorics