排序的代价(索引排序)

总时间限制: 10000ms
单个测试点时间限制: 5000ms
内存限制: 65536kB

描述
现有一排装满货物的箱子,重量各不相同(都已标示在箱子上),为了进行后面的工作,需要将这些箱子按轻重有序放置,但只有一名工作人员来完成这项工作,由于空间有限,他只能通过不断交换两个箱子(可不相邻)的位置的方式来实现箱子的排序。他知道这样一定可以完成任务,但搬箱子很累,所以他希望找到一种最省力的方式来完成工作,假设一次交换两个箱子的代价为这两个箱子的重量之和,那么这项工作的总代价为此过程中所有交换的代价之和,请帮助他计算排列这些箱子的最小代价。

输入
输入包含多个数据实例,每个实例独占一行,每行数据是以空格分隔的非负整数,其中第一个整数表示箱子的个数(n),接下来为n个不同的正整数,分别表示n个箱子的重量,其顺序表示了箱子的初始顺序;当n=0时表示输入结束。

输出
对每个有效数据实例(n!=0)都输出一个整数,独占一行,表示该实例中排序箱子的最小代价。 样例输入 3 3 2 1 4 8 1 2 4
5 1 8 9 7 6 6 8 4 5 3 2 7 0 样例输出 4 17 41 34

提示
示例解释: 共有4个有效数据实例:
第一个数据实例为3 2 1,通过交换重为3和1的箱子即可,总代价为3+1=4; 第二个数据实例为8 1 2 4,代价最小的交换过程为
1↔2,1↔4,1↔8,总代价为(1+2)+(1+4)+(1+8) = 17; 第三个数据实例为1 8 9 7 6,代价最小的交换过程为
1↔6,1↔9,1↔7,1↔8,1↔6,总代价为(1+6)+(1+9)+(1+7)+(1+8)+(1+6)=41; 第四个数据实例为8 4
5 3 2 7,代价最小的交换过程为 3↔5,3↔4,2↔7,2↔8,总代价为(3+5)+(3+4)+(2+7)+(2+8)=34。

请注意边界条件和IO,n可能很大。

#include iostream
#include cstring
#include algorithm
using namespace std;

const int MAXN = 1000005;
const int INF = 0x7fffffff;
int a[MAXN], idx[MAXN], vis[MAXN];
int n;

bool cmp(int i, int j) {
    return a[i]  a[j];
}

int cnt = 0;
int cur_min = INF; /* min element on the cycle */

/**
 * @return sum of elements on the cycle 
 */
int dfs(int cur)
{
    vis[cur] = 1;
    ++cnt;
    cur_min = min(cur_min, a[cur]);
    if (!vis[idx[cur]]) {
        int s = a[cur] + dfs(idx[cur]);
        return s;
    }
    else 
        return a[cur];
}

int main()
{
    while (scanf("%d", n) == 1) {
        if (n == 0)
            break;
        memset(vis, 0, sizeof(vis));
        int minv = INF; /* min element of whole array */
        for (int i = 0; i  n; ++i) {
            scanf("%d", a[i]);
            idx[i] = i;
            minv = min(minv, a[i]);
        }
        sort(idx, idx+n, cmp);
        int ans = 0;
        for (int i = 0; i  n; ++i) 
            if (!vis[i]) {
                cnt = 0, cur_min = INF;
                /* 
                 * Choice 1: swap using the min element of current cycle, cnt-1 round in total
                 * Choice 2: swap using the min element of whole array, cnt+1 round in total(1 more to initiaze, 1 more to restore)
                 */
                ans += dfs(i) + min((cnt-2)*cur_min, (cnt+1)*minv+cur_min);
            }
        printf("%d\n", ans);
    }
    system("pause");
    return 0;
}
最新回复(0)
/jishuyeH1Hx9HxfpWs0IJ2Ll8SJUfrRH7aGN5cY7dq_2B6esr8_3D4794678
8 简首页