P1327 题解
考试的时候考到了,被老师认定为最简单的一题,结果一车暴力人……
考场想到了一个比较神奇的做法,但是没有证明出来,不过最后还是过掉了这道题。
思路
首先把
以样例为例,
从
1 3
2 5
3 2
4 4
5 7
6 1
7 6
8 8
也就是这个样子:
(其中
可以发现有两个点数为
证明
这里讲的是只有一个环的情况,因为环和环之间并没有关系,所以遇到多个环直接求和就好了。
首先,我们的最终目标肯定是把图拆成
我们考虑有向边的意义,发现这就是它想要去到的位置,那么我们的每次交换,就尽量地让它们交换到想要的位置。
比如在上图中,我们交换
交换后的图如下:
可以发现在最优决策下,每次交换一定会将环里面的一个点拉出来变成自环。而拉
代码
#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;
}