luogu 1327 数列排序

题意

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

思路

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

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

Code

#include <bits/stdc++.h>
#define maxn 100010
using 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;
}

2017 ACM-ICPC 亚洲区(南宁赛区)网络赛 J.Minimum Distance in a Star Graph

题意

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

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

思路

找循环节。

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

Code

#include <bits/stdc++.h>
using namespace std;
#define maxn 1010 int 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;
}
05-11 19:23