题目链接：OpenJudge - 4:排序的代价

题目

总时间限制: 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个有效数据实例：
第一个数据实例为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可能很大。

（注：题干没有给 $n$ 的数量级，洛谷上是 $10^5$ .）

思路

这题好，锻炼思维.
首先感觉不好下手. 做过一个形似的题，问的是：

问题 1：求为了给一个 $n$ 元序列排序所需最少的交换两个相邻元素的次数.

那里分析可以发现答案恰等于逆序数，构造过程如下：先将最小的元素 $m$ 通过逐次交换移到它应在的位置 $targ=0$ ，移动次数等于 $targ$ 和原始位置 $pos$ 的差，即等于问题“有几个元素在 $m$ 左边且大于 $m$ ”的答案；对第 $k$ 小的元素重复即可. 但这题不要求相邻，而且每次交换都有个权值，跟逆序对应该没什么关系.

那么很自然就要问如下的问题：

问题 2：求为了给一个 $n$ 元序列排序所需最少的交换两个任意元素的次数.

问题 2 的交换是完全自由的，这增加了难度. 显然排序的规则这时也不重要，我们只想把原先的 $n$ 个数置换到某种次序上.
置换. 以前写着玩，用程序求将任何一个置换迭代进行的结果以及周期，发现置换经常不像一眼看上去那么成整体：随意写一个置换，它很容易分成几个小块，每一块很快就进入循环. 比如置换 $1,2,3,4,5,6,7,8,9,10→2,3,1,4,5,7,6,10,8,9$ 中， $8,9,10$ 和 $1,2,3$ 会产生两个周期为 $3$ 的循环， $6,7$ 产生一个周期为 $2$ 的循环，而 $4$ 和 $5$ 位置根本没变、是周期为 $1$ 的自循环.

事实 1：有些数，或者说有些位置上的数是成环的.

这样问题 2 节省交换次数的思路就有了一个：只换每个环内的数，不换环间数. 因为集合 $\{环包含的位置\}=\{环包含的数所应在的目标位置\}$ .
在继续之前，需要定义什么是环. 不难想到一种刻画环的方式：设每个位置 $i$ 上当前的数应当在的位置是 $targ(i)$ ，那么想象从 $i$ 点跳到 $targ(i)$ 点，再跳到 $targ(targ(i))$ 点......这样最终会跳回 $i$ 点，此时跳跃停止，形成的是一个环.
于是我们面对的就不是一个数组而是一张图了. 图有 $n$ 个顶点，对应数组的 $n$ 个位置，每个点 $i$ 的入度和出度都是 $1$ ，出边指向的点 $next(i)$ 就是 $targ(i)$ .

这种描述下，交换两个位置 $i,j$ 上的数意味着什么？可以认为是在交换出边的终点 $next(i),next(j)$ . 想象一下，这显然会产生如下效果：

事实/操作 2：交换环上 $i,j$ 两处的箭头终点后，环被分为两个子环.

即每次环内交换会使环数严格增加 $1$ . 没有其它操作可以加得更多. 由于目标是把所有点都变成自环，使环数达到 $n$ ，问题 2 的答案就应该是 $n-c$ ，其中 $n$ 为数组大小， $c$ 为环数.

接下来考虑原始问题：

问题 3：称一次交换的代价为所交换的二数之和. 允许任意交换元素. 求为了给一个 $n$ 元序列排序所需最小的交换总代价.

问题 3 应该与问题 2 有紧密的关系了，并且要分析交换的具体步骤.
首先，尽量做环内交换的思路应该大致上不变，所以我们先分析环数最少，即为 $1$ 的情形.
怎么把一个大小为 $size$ 的环用尽可能小的代价拆成 $size$ 个自环呢？考虑贪心. 是每次找到环内的两个最小权值点，执行操作 2 拆成两个环，各自再继续吗？
一开始，我也是这样猜测的，但第二组样例 $8\space1\space2\space4$ 的做法是轮换使用最小元 $1$ ，直接否定了这个策略. 那么轮换使用最小元实质上是什么？先看操作 2 在交换邻点时的特例.

事实/操作 2-1：交换环上 $i,next(i)$ 两处的箭头终点后，环被分为两个子环，其中一个是自环 $next(i)→next(i)$ .

即交换两个邻点相当于把第二个点从环上拆下来. 看来我们只用把最小元 $min$ 与下个邻点挨个交换，就能解决一个环的情况了. 数学上也容易证明这样的代价最小（如果只有这个环）. 若具体算出这个代价，它是 $min×(size-1)+\Sigma$ ，其中 $\Sigma$ 是环中去掉最小元的点权值和. 我们称这是这个环的normal_cost值.

若有多个环，自然打算对每个环都这样做. 然而如此是无法解释第三组样例 $1\space8\space9\space7\space6$ 的操作的，该做法强行把 $1$ 拉进了后面的四元环 $8\space9\space7\space6$ 中，最后又将其解放出来. 由于后四个数太大，最后的代价还真的更小. 拉进一个环具体是说，

事实/操作 3：交换环 $C$ 内一点 $i$ 与某个成自环点 $o$ ，将会使 $o=next(i),next(i)=next(o)$ ，从而将 $o$ 纳入环 $C$ .

因此，对于每个环的处理我们还有一种备选方案：先把全局最小元与环内最小元交换（假定全局最小元及其所在的环已经处理完，是自环），然后对新的大小为 $size+1$ 的环轮换用全局最小元. 称这样做的代价为环的alternative_cost值，其值为 $opt×size+\Sigma+min+(opt+min)$ ，其中 $opt$ 为全局最小.

只需算出每个环的normal_cost、alternative_cost的较小者并求和，就可以得出总最小代价了.

确定每个点的 $next()$ （即该处值在排序后的序数）需要对序列排序，复杂度 $O(n \log n)$ ；DFS 找到每个环并求出两个代价值需要 $O(n)$ 的复杂度. 算法总时间复杂度 $O(n\log n)$ .

代码：

#include <bits/stdc++.h>

#define INF 1e9
#define IOS_SPEED std::ios::sync_with_stdio(false)

using std::cin;
using std::cout;
using std::vector;
using std::unordered_map;
using std::deque;
using std::sort;
using std::min;

typedef long long lli;

class cycle{ // 单个环
    public:
        vector<int> contn; // 环内点的位置/下标
        int min_val; lli sum; // 环内最小权值及权值和
        static int min_min_val; // 全局最小权值
        ~cycle(){contn.clear();}
        lli normal_cost(){return sum+(contn.size()-2)*min_val;}
        lli alternative_cost(){return sum+(contn.size()+1)*min_min_val+min_val;}
        lli actual_cost(){return min(normal_cost(), alternative_cost());} // 两种代价的较小者
};

int cycle::min_min_val = INF;

int size; // 数组大小
vector<int> val, sorted; // val: 原始数组; sorted: 排序后的数组
unordered_map<int, int> order; // order[x]: 值 x 应该出现在的位置, 本题中不会冲突
vector<cycle> cycles; // 所有环
deque<bool> visited; // DFS 寻环防止无限递归的记录数组

void build_cycle(int pos){ // 建立单个环
    if(visited[pos]) return;
    visited[pos] = true;
    cycles.back().contn.push_back(pos);
    cycles.back().min_val = min(cycles.back().min_val, val[pos]);
    cycles.back().sum += val[pos];
    build_cycle(order[val[pos]]);
}

lli sum_of_cycle_costs(){ // 建立所有环并求出答案
    cycle::min_min_val = sorted[0];
    for(int i=0; i<size; i++){
        if(!visited[i]){
            if(i==order[val[i]]){visited[i] = true; continue;}
            cycles.push_back({{}, (int)INF, 0});
            build_cycle(i);
        }
    }
    lli answer = 0;
    for(auto &i: cycles) answer += i.actual_cost();
    return answer;
}

int interface(){
    IOS_SPEED; cin >> size;
    if(size==0) return 1;
    int new_elem;
    for(int i=0; i<size; i++){
        cin >> new_elem;
        val.push_back(new_elem); sorted.push_back(new_elem); visited.push_back(false);
    }
    sort(sorted.begin(), sorted.end());
    for(int i=0; i<size; i++) order[sorted[i]] = i;
    cout << sum_of_cycle_costs() << "\n";
    val.clear(); sorted.clear(); order.clear(); cycles.clear(); visited.clear();
    return 0;
}

int main()
{
    while(1) if(interface()) break;
    return 0;
}

[OpenJudge 4266] 排序的代价〔分治、贪心〕

[OpenJudge 4266] 排序的代价〔分治、贪心〕

题目

思路

相关阅读更多精彩内容

友情链接更多精彩内容