ACM模版

描述

题解

这个题是 CF 的一个题，但不是原题，题目弱化了，数据强化了，一开始想着一个经典算法——使序列有序的最少交换次数，可是意志不坚定的我还是点开了评论区，发现这个要用贪心写，可是发现写来写去就是过不去，一直 TLE，后来用栈写（代码 One），需要右移的入栈，遇见左移的时候出栈交换移动，可是最后依然是 TLE 了……

后来我佐学姐用使序列有序的最少交换次数的代码的变种（代码 Two）提交过了，而我一开始竟然怕结果不是最优的，而直接放弃了这种写法，坑死了……这个题就是一个经典算法的变种~~~

代码

One：

// TLE
#include <iostream>
#include <cstdio>
#include <stack>

using namespace std;

const int MAXN = 2e5 + 10;

int n;
int p[MAXN];
int s[MAXN];
int t[MAXN];

stack<pair<int, int> > spii;

int main(int argc, const char * argv[])
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", p + i);
    }
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", s + i);
        t[s[i]] = i;
    }
    for (int i = 1; i <= n; i++)
    {
        p[i] = t[p[i]];
    }

    int res = 0;
    for (int i = 1; i <= n; i++)
    {
        if (p[i] > i)
        {
            spii.push(make_pair(i, p[i]));
        }
        else if (p[i] < i)
        {
            int pos = spii.top().first;
            res += i - pos;
            swap(p[i], p[pos]);
            spii.pop();
            if (!spii.empty())
            {
                i = spii.top().first;
            }
            else
            {
                i = pos;
            }
        }
    }

    cout << res << '\n';

    return 0;
}

Two：

#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long ll;

const int MAXN = 2e5 + 10;

int A[MAXN];
int B[MAXN];
bool vis[MAXN];

int abs(int a)
{
    return a < 0 ? -a : a;
}

int main ()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", A + i);
    }
    int b;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &b);
        B[b] = i;
    }
    for (int i = 1; i <= n; i++)
    {
        A[i] = B[A[i]];
    }

    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        if (vis[i])
        {
            continue;
        }
        ll sum = 0;
        for (int j = i; !vis[j]; j = A[j])
        {
            sum += abs(j - A[j]);
            vis[j] = true;
        }
        ans += sum / 2;
    }

    printf("%lld\n", ans);

    return 0;
}

参考

《使序列有序的最少交换次数》