洛谷P2127 序列排序 题解

题目链接：P2127 序列排序

题意：

cxy 有一个 $n$ 个数的整数序列，这个序列的中的数两两不同。cxy 每次可以交换序列中的任意两个数，代价为这两个数之和。cxy 希望将整个序列升序排序，问 cxy 需要的最小代价是多少？

输入格式：

第一行，一个整数 $n$ 。

第二行，$n$ 个整数，表示 cxy 的序列。

输出格式：

一行，一个整数，表示 cxy 需要的最小代价。

数据范围：

对于全部的数据，$1\le n \le 10^5$ ，输入数据中的其他整数均为正整数且不超过 $10^9$。

属于是DP学傻了。还记得这篇么 无序数组交换任意两个元素 最少交换次数

显然这道题就是那个题的带权版。考虑贪心。

对于每个数，我们将它与它最终位置连有向边，最终显然会形成若干个环。

对于每个环，第一种方法是用它的最小值去一个个交换（逆连边方向），显然这样是优的

第二种方法是这题的关键。我们可以用环外的全局最小值去代替这个最小值换一遍。

考虑证明算法的正确性。

首先对于环内的每个点，交换一次一定减少一个错位的数。

环上任意一个点做这样的交换都能完成环内的排序。故选择最小值最优。

而环外最小值的引入等价于花费一定代价改变环内最小值，与其他环计算贡献独立。$\square$

然后就是实现的问题了。事实上我们不需要建图。

我们只需要用并查集维护环上的信息就可以了。

（有史以来做过最数据结构的并查集题，但是姑且可以算图论题？）

时间复杂度 $O(n \log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5+15))

int n,ans,MIN,o[N],a[N],f[N],sz[N],sum[N],mn[N];
int cmp(int u,int v) { return a[u] < a[v];}
int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
int g(int i)
{
    return min( (sz[i]-1) * mn[i] + sum[i] - mn[i],
    (sz[i]-1) * MIN + sum[i] - mn[i] + 2 * (MIN + mn[i]) );
}
void merge(int u,int v)
{
    int x = find(u), y = find(v);
    if(x == y) return ;
    if(sz[x] > sz[y]) swap(x,y);
    f[x]=y; down(mn[y], mn[x]);
    sz[y] += sz[x]; sum[y] += sum[x];
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i=1; i<=n; i++)
    {
        cin >> a[i]; f[i] = o[i] = i;
        sz[i] = 1; sum[i] = mn[i] = a[i]; // 结点数、最小值 以及 总和
    }
    sort(o+1, o+1+n, cmp); MIN = a[o[1]];
    for(int i=1; i<=n; i++) if(o[i] != i) merge(o[i], i);
    for(int i=1; i<=n; i++) if(f[i] == i) ans += g(i);
    cout << ans << '\n';
    return 0;
}