首页 > 代码库 > 2845 排序的代价
2845 排序的代价
2845 排序的代价
时间限制: 1 s
空间限制: 32000 KB
题目等级 : 黄金 Gold
题目描述 Description
有一列数，要对其进行排序（升序）。排序只能通过交换来实现。每次交换，可以选择这列数中的任意二个，交换他们的位置，并且交换的代价为二个数的和。排序的总代价是排序过程中所有交换代价之和。先要求计算，对于任意给出的数列，要将其排成升序所需的最小代价。
输入描述 Input Description
输入数据有两行组成。第一行一个数n，表示这列数共有n个数组成，第二行n个互不相同的整数（都是小于1000的正整数），表示这列数
输入可能包含多组测试数据(少于50组)，对于每个输入数据均需要给出对应的输出
输出描述 Output Description
对于每个输入数据，输出最小代价。格式为Case t: min
其中t为数据的编号，从1开始，min为这个数据的最小代价
样例输入 Sample Input
3
3 2 1
4
8 1 2 4
样例输出 Sample Output
Case 1: 4
Case 2: 17
数据范围及提示 Data Size & Hint
n<=1000
分类标签 Tags 点此展开
置换群 群论
题解：
置换群+离散化.
使一个数列恢复递增顺序,那么,他和他要到达的位置的数需要交换,这样就形成了一个置换.
对于一个有向圈的置换,我们可以证明它的最小代价就是这个有向圈中 最小元素*(有向圈的大小-1)+其他数的和-最小元素.
1个大小为n的有向环,至少会进行n-1次交换才能成为n个1元环
当size=1,2 时,它显然成立.
当size>2 时,每次交换1个元素会将圆圈拆成两个互不相交的置换,一直拆下去需要拆n-1次.
然后还有一个问题就是我们可以把一个最小的数拉过来进行交换,这样我们就需要的代价就是,用最小的和有向圈中最小的交换,再让最小的*(有向圈大小-1)
这样这道题就显而易见了,至于不是连续的,我们可以离散化.
AC代码：
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N=1e3+10;int n,cnt,ans,cas;int r[N],a[N],b[N],c[N],s1;int p[N][N],s[N],h[N];bool vis[N];int main(){ while(scanf("%d",&n)==1){ cnt=ans=0; memset(vis,0,sizeof vis); memset(p,0,sizeof p); memset(h,0,sizeof h); for(int i=1;i<=n;i++) scanf("%d",r+i); for(int i=1;i<=n;i++) a[i]=r[i]; sort(a+1,a+n+1);s1=a[1]; for(int i=1;i<=n;i++) b[a[i]]=i; for(int i=1;i<=n;i++) c[i]=b[r[i]]; for(int i=1,t;i<=n;i++) if(!vis[i]){ s[++cnt]=r[t=i]; while(!vis[t]) vis[t]=1,p[cnt][++p[cnt][0]]=r[t],s[cnt]=min(s[cnt],r[t]),h[cnt]+=r[t],t=c[t]; } for(int i=1;i<=cnt;i++){ ans+=min(s[i]*(p[i][0]-1)+h[i]-s[i],s[i]*2+s1*2+s1*(p[i][0]-1)+h[i]-s[i]); } if(!ans) break; printf("Case %d: %d\n",++cas,ans); } return 0;}
2845 排序的代价
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。