题目链接
bzoj1697: [Usaco2007 Feb]Cow Sorting 牛排序
题解
对于一对妞, 每一次交换可以看做一个置换, 初始序列看做轮换的乘
在一个轮换内, 牛牛们是可以互相到达的
我们可以用轮换内代价最小的牛牛来交换其他的牛牛
花费为 sum+min(len-1)-min
还有另一种方案可能更优, 引入置换中的最小元素 minn, 与当前轮换中的最小值交换位置, 花费 minn+min, 像上述一样计算花费 minn(len-1)+(sum-min)
然后在换回去, 总代价 minn*(len+1)+sum+min
贪心一下就好惹
代码
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- using std::max;
- using std::min;
- inline int read() {
- int x=0;char c=getchar();
- while(c<'0'||c>'9') c=getchar();
- while(c<='9'&&c>='0') x=x*10+c-'0',c=getchar();
- return x;
- }
- const int maxn = 100007;
- bool vis[maxn];
- int tmp[maxn],to[maxn],next[maxn],ans=0;
- int main() {
- memset(vis,1,sizeof(vis));
- int n=read(),maxx=-1,minn=0x7fffffff;
- for(int i=1;i<=n;++i) {
- to[i]=tmp[i]=read();
- vis[tmp[i]]=false;
- maxx=max(to[i],maxx);
- minn=min(to[i],minn);
- }
- std::sort(to+1,to+n+1);
- for(int i=1;i<=n;++i) {
- next[to[i]]=tmp[i];
- }
- for(int i=1;i<=maxx;++i) {
- if(vis[next[i]])continue;
- vis[i]=1;
- int p=i,cnt=1,sum=i,tminn=i;
- while(next[p]!=i) {
- p=next[p];cnt++;
- sum+=p;vis[p]=1;
- tminn=min(tminn,p);
- }
- ans+=min(sum+(cnt-2)*tminn,sum+tminn+(cnt+1)*minn);
- }
- printf("%d\n",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2493688.html