luogu 1327 数列排序

题意

给定一个数列\(\{an\}\)，这个数列满足\(ai≠aj(i≠j)\)，现在要求你把这个数列从小到大排序，每次允许你交换其中任意一对数，请问最少需要几次交换？

思路

找循环节。答案即为 (循环节的长度\(-1\)) 对所有循环节求和。

如果只能交换相邻两个，那么就是求逆序对个数。因为交换相邻两个数字的效果是使逆序对个数\(-1\).

Code

#include <bits/stdc++.h>#define maxn 100010using namespace std;typedef long long LL;int a[maxn], b[maxn];bool vis[maxn];map<int, int> mp;int main() {int n;scanf("%d", &n);for (int i = 0; i < n; ++i) {scanf("%d", &a[i]);b[i] = a[i];mp[a[i]] = i;}sort(b, b+n);int ans = 0;for (int i = 0; i < n; ++i) {if (vis[i]) continue;int j = i;while (!vis[j]) {vis[j] = true;j = mp[b[j]];++ans;}--ans;}printf("%d\n", ans);return 0;}

ACM-ICPC 亚洲区（南宁赛区）网络赛 J.Minimum Distance in a Star Graph

题意

给出一个排列，问对其进行多少次操作能得到递增的排列。

一次操作指交换第\(i\)个位置上的数和第\(1\)个位置上的数。

思路

找循环节。

对于包含第一个数字的循环节，交换次数为 (循环节长度\(-1\))；\(otherwise\)，交换次数为 (循环节长度\(+1\)).

Code

#include <bits/stdc++.h>using namespace std;#define maxn 1010int n;char s[100], t[100];int pos[maxn];bool vis[maxn];void work() {char ch;memset(vis, 0, sizeof(vis));memset(pos, 0, sizeof(pos));scanf("%s%s", s, t);for (int i = 0; i < n; ++i) pos[s[i]] = i;int temp = 0, ans = 0; vis[0] = true;while (t[temp] != s[0]) {temp = pos[t[temp]];++ans;vis[temp] = true;}for (int i = 1; i < n; ++i) {if (!vis[i]) {vis[i] = true;int temp = i, len = 0;while (t[temp] != s[i]) {temp = pos[t[temp]];++len;vis[temp] = true;}if (len) ans += len + 2;}}printf("%d\n", ans);}int main() {while (scanf("%d", &n) != EOF) {for (int i = 0; i < 5; ++i) work();}return 0;}