luogu 1327 数列排序 & 2017 ACM-ICPC 亚洲区（南宁赛区）网络赛 J题 循环节

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;

}