题解：P6193 [USACO07FEB] Cow Sorting G

· · 题解

本蒟蒻的第一篇题解，求求管理员大大审核通过 QAQ。

P6193 [USACO07FEB] Cow Sorting G 解题报告。

题意

有一个长度为 n（1 \leq n \leq 10^5）的序列，第 i 个数有一个权值 a_i（1 \leq a_i \leq 10^5, a_i 互不相同）。你可以花费 a_i+a_j 的代价去交换第 i 个元素和第 j 个元素，求将 a 升序排序的最小代价。

分析

这个 a_i+a_j 的代价就很烦，我们先考率题目的弱化。

弱化版

如果不管代价，只要求交换次数最少，答案是什么呢？

举一个例子：

数列 \{5,1,4,3,2\}，最少需要三次操作。

第一次操作：交换 3 和 4，数列变成 \{5,1,3,4,2\}。

第二次操作：交换 1 和 5，数列变成 \{1,5,3,4,2\}。

第三次操作：交换 2 和 5，数列变成 \{1,2,3,4,5\}。

可以证明不存在更少的操作次数。

可以发现，我们的操作策略就是把一个元素移到它该去的地方。

我们将一个元素与它要去的位置所在的元素连边（如元素 5 要与在第 5 个位置的元素 2 连边），如下图：

我们可以发现，图是由若干个环组成的。

感性证明也非常简单，每个点被连一次，出去一次，入度和出度均是一，这样的图只能是若干个环组成的。

观察上图的环，以环 2 \rightarrow 1 \rightarrow 5 \rightarrow 2 举例子。

我们可以发现 2,5,1 虽然不在自己应该在的位置，但是如果把它们看成整体，对于整个序列来说它们占据了排好序后 2,5,1 应该在的位置，所以对于整个序列来说是有序的，它们只是自身内部无序而已。所以只需要环内换序就可以了。

而对于一个含有 n 个元素的环，只要交换 n-1 次（一次操作排好一个元素，最后一个不用排）。所以，答案就是元素的数量减去环的数量。

严格的证明较复杂，可以参考 这篇文章。

弱化版核心代码：

ans=n;
for(int i=1;i<=n;i++){
    if(vis[i])continue;
    int now=i;ans--;
    while(!vis[now]){
        vis[now]=1;//打标记
        now=a[now];//遍历下一个结点
    }
}

由于每个结点只经过一次，时间复杂度是 \mathcal{O}(n) 的。

原题

扯了这么多，让我们回到正轨。

我们将上面的方法迁移过来，先找到一个元素它排序后在哪里，这可以用二分或排序解决，然后建环。

那么现在的问题就变成了：

把一个环内的元素有序排列的最小代价。

每个元素要回到原位置，最少也得交换一次。而像这样简单强势的交换，一共有 siz-1 次（siz 是环的大小）。只需要利用圈里面最小的那个当苦力参与交换即可，此时代价为 (siz - 2)\times Min + Sum，其中 Sum 表示环中所有元素之和，Min 表示环中最小的元素（Min 与其它所有元素做了 siz-1 次交换，Sum 中包含了一个 Min，所以是 (siz - 2)\times Min + Sum）。

当你自信满满的拿着代码甩在这道题脸上时，你会发现这道题拿着 WA 甩了你一脸。

问题出在哪呢？我们来看下面这个图：

按照我们原来的的方式，我们会拿 9997 分别与 9998 到 10000 进行交换，代价是 (9997+ 9998)+(9997 + 9999)+(9997 + 10000)=59988。如果我们将外面的 1 介入呢：

1.先将外部最小的与内部最小的交换，代价为 (1+9997)=9998。

2.再将外部最小代替以前内部最小进行交换，代价为 (1+9998)+(1+9999)+(1+10000)=30000。

3.最后将外部最小的与内部最小交换回来，代价为 (1+9997)=9998。

总代价为 9998+30000+9998=49996 < 59988。

关于为什么要与内部最小的交换的简要证明：

设外部最小 Min（这应该很好理解）与内部权值为 X 的元素交换。

  • 第一、三步的代价为 Min+x。

  • 第二步的代价为 (siz-2)\times Min+(Sum-x+Min)（定义同上）。

总代价为 x+(siz+1)\times Min+Sum。

由于 Sum,siz,Min 是定值，当 x 最小时代价最小。

所以，共有两种调换办法，大部分人都会想到利用圈里面最小的那个参与交换，还有一个办法就是把全局最小的调入圈里，弄好了再还回去。

此时，代价为 \min(Sum+( siz - 2 ) \times Min1,(siz+1)\times Min2+Sum+Min1)，其中 siz 是环的大小， Sum 表示环中所有元素之和， Min1 表示环中最小的元素， Min2 表示全局最小的元素。

每个元素只折腾一次，故核心时间复杂度为 \mathcal{O}(n)。

瓶颈在于排序或二分的 \mathcal{O}(n \log n)。

注意开 long long。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=200005;
int n,b[maxn],a[maxn],nxt[maxn],ans,Min1=(int)1<<60;;
bool vis[maxn];
int read(){
    char ch=getchar();int ret=0,f=1;
    while(ch<'0'||ch>'9'){if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') ret=ret*10+(ch&15),ch=getchar();
    return ret*f;
}
int find(int x){//二分枚举每个数排序后的排名
    int L=1,R=n,mid,ans;
    while(L<=R){
        mid=L+R>>1;
        if(b[mid]==x)return mid;
        if(b[mid]<x)L=mid+1; 
        if(x<b[mid])R=mid-1;
    }
}
signed main(){
//  freopen("csort.in","r",stdin);
//  freopen("csort.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++)b[i]=a[i]=read(),Min1=min(Min1,a[i]);
    sort(b+1,b+1+n);
    for(int i=1;i<=n;i++)nxt[i]=find(a[i]);
    for(int i=1;i<=n;i++){
        if(vis[i])continue;
        int now=i;
        int Min2=(int)1<<60,cnt=0,sum=0;
        while(!vis[now]){//遍历环
            cnt++;sum+=a[now];vis[now]=1;
            Min2=min(Min2,a[now]);
            now=nxt[now];
        }
        int now1=(cnt-1)*Min2+sum-Min2;
        int now2=cnt*Min1+sum+Min2+Min1;
        ans+=min(now1,now2);//计算代价
    }
    printf("%lld\n",ans);
    return 0;
}

都看到这里了，能不能给个赞呢？

有不懂随时@我。

蒟蒻第一篇题解写得不好请见谅。