首页 > 代码库 > 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 排序的代价