BZOJ 1697: [Usaco2007 Feb]Cow Sorting牛排序

Description

农夫JOHN准备把他的 N(1 <= N <= 10,000)头牛排队以便于行动。因为脾气大的牛有可能会捣乱,JOHN想把牛按脾气的大小排序。每一头牛的脾气都是一个在1到100,000之间的整数并且没有两头牛的脾气值相同。在排序过程中,JOHN 可以交换任意两头牛的位置。因为脾气大的牛不好移动,JOHN需要X+Y秒来交换脾气值为X和Y的两头牛。 请帮JOHN计算把所有牛排好序的最短时间。

Input

第1行: 一个数, N。

第2~N+1行: 每行一个数,第i+1行是第i头牛的脾气值。

Output

第1行: 一个数,把所有牛排好序的最短时间。

题解:

置换群。

参考hzwer

1.找出初始状态和目标状态。明显,目标状态就是排序后的状态。
2.画出置换群,在里面找循环。例如,数字是8 4 5 3 2 7
明显,目标状态是2 3 4 5 7 8,能写为两个循环:
(8 2 7)(4 3 5)。
3.观察其中一个循环,明显地,要使交换代价最小,应该用循环里面最小的数字2,去与另外的两个数字,7与8交换。这样交换的代价是:
sum - min + (len - 1) * min
化简后为:
sum + (len - 2) * min
其中,sum为这个循环所有数字的和,len为长度,min为这个环里面最小的数字。

4.考虑到另外一种情况,我们可以从别的循环里面调一个数字,进入这个循环之中,使交换代价更小。例如初始状态:
1 8 9 7 6
可分解为两个循环:
(1)(8 6 9 7),明显,第二个循环为(8 6 9 7),最小的数字为6。我们可以抽调整个数列最小的数字1进入这个循环。使第二个循环变为:(8 1 9 7)。让这个1完成任务后,再和6交换,让6重新回到循环之后。这样做的代价明显是:
sum + min + (len + 1) * smallest
其中,sum为这个循环所有数字的和,len为长度,min为这个环里面最小的数字,smallest是整个数列最小的数字。

5.因此,对一个循环的排序,其代价是sum - min + (len - 1) * min和sum + min + (len + 1) * smallest之中小的那个数字。

6.我们在计算循环的时候,不需要记录这个循环的所有元素,只需要记录这个循环的最小的数及其和。

7.在储存数目的时候,我们可以使用一个hash结构,将元素及其位置对应起来,以达到知道元素,可以快速反查元素位置的目的。这样就不必要一个个去搜索。

代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>

//by zrt
//problem:
using namespace std;
typedef long long LL;
const int inf(0x3f3f3f3f);
);
int n;
];
];
];
int mn;
];
int solve(int x){
    int sum=a[x];
    vis[x]=;
    int k=x;
    int minn=a[x];
    ;
    ;
    )*minn,sum+minn+(l+)*mn);
}
int main(){
    #ifdef LOCAL
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    scanf("%d",&n);
    mn=inf;
    ;i<=n;i++){
        scanf("%d",&a[i]);
        to[a[i]]=i;
        b[i]=a[i];
        mn=min(a[i],mn);
    }
    sort(b+,b+n+);
    ;
    ;i<=n;i++){
        if(!vis[i]){
            ans+=solve(i);
        }
    }
    printf("%d\n",ans);
    ;
}
上一篇:Android--绑定服务调用服务的方法


下一篇:DataHub产品测试