ACM模版

描述

题解

看了这道题，标记着贪心算法，但是吭哧吭哧了好久也没有想到如何贪心才是最贪心的策略，每次总是感觉有纰漏，无法想到最全的策略。找了找大神的题解，茅厕顿开，真是自己太年轻了。

找到一篇 say_c_box 的详细题解，打开了我的思维，着实不错。

以下是其核心题解：

那么针对每一个机器怎样交换的代价最小？
很容易想到要尽可能的使重量小的机器交换次数多，重量大的物品交换次数少。

所以策略就是两种，我们把机器按重量从小到大排序，并记录下它原始的位置。从小到大遍历。把某个重量的机器放到它应该在的位置上，必然要把占了这个位置的机器也做移动，依此类推下去。

第一种策略：
用这些机器（假如为x个）中重量最小的依此和需要交换的机器交换。这种情况下，其它所有机器交换一次，最小重量的机器交换x次。
第二种策略：
用所有机器中重量最小的依此和这些机器交换。再把重量最小的换回到第一个位置。这种情况下，重量最小的那个交换x+2（换出去换回来各一次）次，其他的交换一次.但有一个特殊的，最后把最小的那个交换回来的要多交换一次。也就是两次。我们自然会选取重量最小的那个作为特殊机器。

我一开始少考虑了一种策略，也就是第二种策略，结果 AC 了一小半，WA 了一大部分。看了这个大神的题解后，才算是理解了一些，这种贪心的问题，真是一个思维性极强的问题。

代码

#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 5e4 + 10;

struct machin
{
    int w;  // 重量
    int p;  // 原来的位置
} M[MAXN];

long long minW;   // 所有中W最小的
int vis[MAXN];

long long solve(int k)
{
    long long minW_ = M[k].w; // 此次需要交换的部分中 W 最小的
    int cnt = 0;        // 交换次数
    long long wSum = M[k].w;
    int p = M[k].p;
    vis[k] = 1;

    while (k != p)
    {
        wSum += M[p].w;
        vis[p] = 1;
        p = M[p].p;
        cnt++;
    }
    return wSum + min(minW_ * (cnt - 1), minW * (cnt + 2) + minW_);
}

bool cmp(const machin a, const machin b)
{
    return a.w < b.w;
}

int main(int argc, const char * argv[])
{
    int N;
    cin >> N;

    for (int i = 0; i < N; i++)
    {
        cin >> M[i].w;
        M[i].p = i;
    }
    sort(M, M + N, /* [](const machin a, const machin b){ return a.w < b.w; } */ cmp);
    minW = M[0].w;

    long long ret = 0;
    for (int i = 0; i < N; i++)
    {
        if (!vis[i])
        {
            ret += solve(i);
        }
    }

    cout << ret << '\n';

    return 0;
}