当前位置：首页 > news >正文

UVa 1016 Silly Sort

news 2026/5/14 10:32:59

题目描述

你的弟弟有一项作业，需要一些帮助。老师给了他一个数字序列，要求按升序排序。在排序过程中，可以交换两个数字的位置。每次交换都有一个成本，即两个数字的和。

你需要编写一个程序，确定排序数字序列的最小成本。

输入格式

输入文件包含多个测试用例。每个测试用例由两行组成：

第一行是一个整数n(n>1)n (n > 1)n(n>1)，表示要排序的数字个数
第二行是nnn个不同的正整数（每个数都小于100010001000），表示要排序的数字

输入以一个单独一行的000结束。

输出格式

对于每个测试用例，输出一行，包含测试用例编号和排序该测试用例数字的最小成本。每个测试用例输出后输出一个空行。

样例输入

3 3 2 1 4 8 1 2 4 5 1 8 9 7 6 6 8 4 5 3 2 7 0

样例输出

Case 1: 4 Case 2: 17 Case 3: 41 Case 4: 34

题目分析

这是一个最小成本排序问题，我们需要找到将序列排序所需的最小交换成本。关键在于理解交换操作的本质和如何最小化总成本。

问题本质

将原序列看作一个排列，排序过程就是将这个排列通过交换操作变为恒等排列。每次交换两个数字的成本是它们的和。

关键观察

循环分解：任何排列都可以分解为若干个不相交的循环。例如：
- 原序列：3 2 13\ 2\ 1321
- 排序后：1 2 31\ 2\ 3123
- 排列为(1→3→1)(1\rightarrow 3\rightarrow 1)(1→3→1)一个循环
循环内交换策略：对于一个长度为kkk的循环，有两种主要的交换策略：
策略1：仅使用循环内的最小值进行交换
- 成本 =cycleSum+(k−2)×cycleMin\texttt{cycleSum} + (k-2) \times \texttt{cycleMin}cycleSum+(k−2)×cycleMin
- 解释：用循环内最小值与其他k−1k-1k−1个元素各交换一次
策略2：借助全局最小值进行交换
- 成本 =cycleSum+cycleMin+(k+1)×globalMin\texttt{cycleSum} + \texttt{cycleMin} + (k+1) \times \texttt{globalMin}cycleSum+cycleMin+(k+1)×globalMin
- 解释：先将全局最小值引入循环，完成交换后再将其恢复
策略选择：对于每个循环，我们选择两种策略中成本较小的那个。

算法步骤

读入数据直到n=0n = 0n=0
对每个测试用例：
- 复制原数组并排序，建立位置映射
- 标记已访问元素
- 找出所有循环，对每个循环计算两种策略的成本
- 累加最小成本到总成本
输出结果

解题思路详解

循环分解的重要性

在排列中，每个元素都有一个"应该去的位置"。当我们跟踪一个元素从当前位置到它应该在的位置，再从那个位置跟踪下一个元素，最终会形成一个循环。

例如样例1：

原序列：3 2 13\ 2\ 1321
排序后：1 2 31\ 2\ 3123
333应该在位置222（从000开始编号），位置222上是111，111应该在位置000，位置000上是333，形成一个循环(0→2→0)(0\rightarrow 2\rightarrow 0)(0→2→0)

成本计算原理

对于长度为kkk的循环：

策略1的成本推导：

需要k−1k-1k−1次交换才能让循环内所有元素归位
如果每次都用循环内最小值参与交换，总成本 =(k−1)×cycleMin+(cycleSum−cycleMin)(k-1) \times \texttt{cycleMin} + (\texttt{cycleSum} - \texttt{cycleMin})(k−1)×cycleMin+(cycleSum−cycleMin)
简化后：cycleSum+(k−2)×cycleMin\texttt{cycleSum} + (k-2) \times \texttt{cycleMin}cycleSum+(k−2)×cycleMin

策略2的成本推导：

先将全局最小值与循环内最小值交换：成本 =globalMin+cycleMin\texttt{globalMin} + \texttt{cycleMin}globalMin+cycleMin
用全局最小值完成循环内其他k−1k-1k−1次交换：成本 =(k−1)×globalMin+(cycleSum−cycleMin)(k-1) \times \texttt{globalMin} + (\texttt{cycleSum} - \texttt{cycleMin})(k−1)×globalMin+(cycleSum−cycleMin)
最后将全局最小值恢复：成本 =globalMin+cycleMin\texttt{globalMin} + \texttt{cycleMin}globalMin+cycleMin
总成本 =cycleSum+cycleMin+(k+1)×globalMin\texttt{cycleSum} + \texttt{cycleMin} + (k+1) \times \texttt{globalMin}cycleSum+cycleMin+(k+1)×globalMin

为什么策略222可能更优

当循环内最小值远大于全局最小值时，借助全局最小值进行交换可以显著降低成本。特别是当循环较长且循环内元素较大时，策略222的优势更加明显。

复杂度分析

时间复杂度：O(nlog⁡n)O(n \log n)O(nlogn)，主要来自排序操作
空间复杂度：O(n)O(n)O(n)，用于存储原数组、排序数组和访问标记

代码实现

// Silly Sort// UVa ID: 1016// Verdict: Accepted// Submission Date: 2025-11-09// UVa Run Time: 0.010s//// 版权所有（C）2025，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(){intcaseNum=1;intn;while(cin>>n&&n!=0){vector<int>arr(n);for(inti=0;i<n;i++)cin>>arr[i];vector<int>sortedArr=arr;sort(sortedArr.begin(),sortedArr.end());// 位置映射：值 -> 在排序后的索引vector<int>pos(1000,-1);for(inti=0;i<n;i++)pos[sortedArr[i]]=i;vector<bool>visited(n,false);intglobalMin=sortedArr[0];inttotalCost=0;for(inti=0;i<n;i++){if(visited[i]||pos[arr[i]]==i)continue;// 找到一个循环intcycleMin=INT_MAX;intcycleSum=0;intcycleLen=0;intcur=i;while(!visited[cur]){visited[cur]=true;cycleLen++;cycleSum+=arr[cur];if(arr[cur]<cycleMin)cycleMin=arr[cur];cur=pos[arr[cur]];}// 策略1：仅用循环内最小值交换intcost1=cycleSum+(cycleLen-2)*cycleMin;// 策略2：借助全局最小值交换intcost2=cycleSum+cycleMin+(cycleLen+1)*globalMin;totalCost+=min(cost1,cost2);}cout<<"Case "<<caseNum<<": "<<totalCost<<"\n\n";caseNum++;}return0;}