P1327 题解

· · 题解

考试的时候考到了,被老师认定为最简单的一题,结果一车暴力人……

考场想到了一个比较神奇的做法,但是没有证明出来,不过最后还是过掉了这道题。

思路

首先把 a 排序,设排序后的数组为 b。那么对于 a 的每一个数,二分其在 b 的位置,并从在 a 的下标到在 b 的下标连一条有向边。这样显然每个结点都是入度为 1 出度为 1 的,因此必然形成若干个环。设共有 k 个环,第 i 个环的点数为 c_i,那么答案即为:

\sum\limits_{i=1}^k(c_i-1)

以样例为例,a=\{8,23,4,16,77,-5,53,100\},那么排序后的 b=\{-5,4,8,16,23,53,77,100\}

a 的所有数出发,到 b 的那个数的位置,那么所有的边即为:

1 3
2 5
3 2
4 4
5 7
6 1
7 6
8 8

也就是这个样子:

(其中 48 是自环)

可以发现有两个点数为 1 的环和一个点数为 6 的环,那么答案即为:

(1-1)+(1-1)+(6-1)=5

证明

这里讲的是只有一个环的情况,因为环和环之间并没有关系,所以遇到多个环直接求和就好了。

首先,我们的最终目标肯定是把图拆成 n 个自环,这样就表示排好序了。

我们考虑有向边的意义,发现这就是它想要去到的位置,那么我们的每次交换,就尽量地让它们交换到想要的位置。

比如在上图中,我们交换 (2,3)2 在到达了自己的位置之后,直接变成自环。而 3 并没有到达自己的位置,所以依旧有一条有向边连向 5

交换后的图如下:

可以发现在最优决策下,每次交换一定会将环里面的一个点拉出来变成自环。而拉 c_i-1 个点之后,最后一个点也自动变成自环,所以答案即为 c_i-1

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN 100001

int n, u, v, ans, cnt;
int a[MAXN], b[MAXN], pos[MAXN];
vector<int> e[MAXN];
bitset<MAXN> vis;
queue<int> que;

void bfs(int s){
    cnt = -1;
    que.push(s);
    while (!que.empty()){
        u = que.front();
        que.pop();
        ++cnt;
        vis.set(u);

        for (auto i: e[u]){
            if (!vis.test(i)) que.push(i);
        }
    }
    ans += cnt;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for (int i(1); i<=n; ++i){
        cin >> a[i];
        b[i] = a[i];
    }
    sort(b+1, b+n+1);
    for (int i(1); i<=n; ++i) e[i].push_back(lower_bound(b+1, b+n+1, a[i])-b);

    for (int i(1); i<=n; ++i){
        if (!vis.test(i)) bfs(i);
    }
    cout << ans;

    return 0;
}