首页 > 代码库 > poj 3270 Cow Sorting (置换群)
poj 3270 Cow Sorting (置换群)
/* 对于每一个群,我们有两种换发: 1.群里换,拿群里最小的数t与其他每个数交换,共k-1次,花费为:sum+(k-2)*t. 2.将这个数列最小的数minn,拉入这个群,与该群最小的数t交换,然后用这个最小的数与其他数交换k-1次,然后再将minn与t换回来,这样 花费为:sum+t+(k+1)*minn 那么最小花费我们取两者中最小的,即sum+min{(k-2)*t,t+(k+1)*minn}. */ # include <stdio.h> # include <algorithm> # include <string.h> # include <iostream> using namespace std; struct node { int id; int num; }; struct node a[10010]; bool cmp(node a1,node a2) { return a1.num<a2.num; } int main() { int sum1,i,minn,n; int b[10010],c[10010]; while(~scanf("%d",&n)) { sum1=0; minn=100010; for(i=1;i<=n;i++) { scanf("%d",&b[i]); a[i].num=b[i]; a[i].id=i; sum1+=b[i]; if(b[i]<minn) minn=b[i]; c[i]=i; } sort(a+1,a+n+1,cmp); for(i=1;i<=n;i++) { int t; if(b[i]!=0) { int count=1; t=b[i]; int d=a[c[i]].id; if(b[d]<t) t=b[d]; while(d!=i) { count++; d=a[d].id; if(b[d]<t) t=b[d]; } int v=(count-2)*t; int w=(count+1)*minn+t; sum1+=min(v,w); b[i]=0; } } printf("%d\n",sum1); } return 0; }
poj 3270 Cow Sorting (置换群)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。