当前位置: 代码迷 >> 综合 >> POJ 3270 Cow Sorting
  详细解决方案

POJ 3270 Cow Sorting

热度:72   发布时间:2023-12-06 03:25:10.0

题目链接:http://poj.org/problem?id=3270

题意:给我们一串值,可以交换任意两个的位置,代价则是两个价值的和,问我们最小花费多少可以使得这串值升序排列。

这个题第一步我们应该找到的是每一位的置换循环节,在循环节中的调整才能够使得这个序列变成升序的,举个例子:6,3,4,2,1,5,最终要把它变成1,2,3,4,5,6,我们移动6,就可以得到6->5->1->6,这就是一个循环节,当然3->4->2->3也是一个循环节,方法找到了,是移动这个循环节内部,现在我们来看看怎么才能达到最优,很容易想到,如果仅仅是循环节内部移动的话,当然是每一步都移动循环节中最小数Min_1,移动k-1次(k为循环节长度)就能达到最终的效果,但是这个一定是最优的吗?可能不是,我们可以先用整个序列中最小的那个数Min来和循环节中最小的那个数交换,然后再进行移动k-1次的步骤,最后再把它移回去。

所以答案应该是min(sum - Min + (k-1)*Min_1, Min_1 + (k+1)*Min;)

#include <cstdio>//置换群-POJ 3270
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 100000+2;
int a[maxn], num[maxn], Max, Min, n, ans;
bool p[maxn];
int main()
{int i,j;Max = 0, Min = 0x3f3f3f3f;scanf("%d",&n);for(int i=1; i<=n; i++){scanf("%d",&a[i]);num[a[i]]++;Max = max(Max, a[i]);Min = min(Min, a[i]);}for(int i=1; i<=Max; i++) num[i] += num[i-1];for(int i=1; i<=n; i++)if(!p[i]){int t = 0, sum = 0, j = i, Min_1 = 0x3f3f3f3f;while(!p[j]){t++;Min_1 = min(Min_1, a[j]);sum += a[i];p[j] = 1;j = num[a[j]];}if(t > 1) ans += sum;if(t >= 2){int s1 = (t-2)*Min_1;int s2 = Min_1 + (t+1)*Min;ans += min(s1, s2);}}printf("%d\n",ans);
}