POJ3270|JDOJ1008 牛排序|Cow Sorting


因为模拟赛题解里面提到了“置换群”的概念,所以便留了一道题来做……

POJ3270 / JDOJ1008 牛排序 Cow Sorting

题目大意:给你一个乱序序列,可将其中元素两两交换,定义两个元素交换代价为这两个元素的和,求将整个序列排成升序最小的交换代价和。


置换群

置换群是什么?

百度百科上有完全的标准解释,但是那是基于数学的解释,对我们计算机竞赛的而言很难理解。

一个置换可以写成若干循环的乘积,那么如果置换求幂的话,一个循环不会跑到另一个循环里面去。
我们可以简单理解为这几个位置的数来回换。

——buptLizer:置换群

那就这样理解吧反正不是很懂数学QwQ

然后,我们便可以开始做这道题了。因为是要排序,而且排序方式十分简单,我们就要先把“置换群”——也就是那些环找出来,我们发现对于每个置换群一共有两种解决方案:

  1. 找出置换群中最小的元素,与置换群中其他元素进行交换,所需代价为sum + min + (len + 1) * smallest。
  2. 把整个序列中的最小元素找出来,与置换群中最小元素交换,然后进行1,然后再次交换回来。

其中,sum为这个循环所有数字的和,len为长度,min为这个环里面最小的数字,smallest是整个数列最小的数字。

使用DFS搜索每一个环,注意在进行搜索的时候必须非常清楚的了解每一个数组,每一个值是什么意思,像我就在DFS当中弄混了元素位置和元素的值,最终莫名其妙WA了50%……在DFS函数中不需要使用栈存储经过的元素,只需要存储一下最小值和元素个数即可。

最终在各种改代码之后AC。

附AC代码:

#include <cstdio>
#include <algorithm>
  
int ans,n,a[100100],b[100100],pos[100100],cnt,tot,minnum;
bool use[100100];
 
void dfs(int target)
{
    if(use[target])
    {
        ans+=std::min(tot-minnum+(cnt-1)*minnum,tot+minnum+(cnt+1)*b[1]);
        return;
    }
    use[target]=true;
    minnum=std::min(minnum,a[target]);
    tot+=a[target];
    cnt++;
    dfs(pos[a[target]]);
    return;
}
  
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    std::sort(b+1,b+n+1);
    for(int i=1;i<=n;++i) pos[b[i]]=i;
    for(int i=1;i<=n;++i)
        if(!use[i])
        {
            minnum=0x7fffffff;
            tot=0;
            cnt=0;
            dfs(i);
        }
    printf("%d",ans);
    return 0;
}

 

声明:TonyZhao's Home|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - POJ3270|JDOJ1008 牛排序|Cow Sorting


不骗了,不骗了。
A Simple OIer fighting tooth and nail.