Codeforces 584E Anton and Ira

时间：2023-12-24 20:17:13

Anton and Ira

我们把点分为三类， 向左走的， 向右走的， 不动的。

最完美的情况就是每个点没有走反方向。

每次我们挑选最右边的向右走的去把向左走的交换过来，这样能保证最优。

#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mk make_pair

#define PLL pair<LL, LL>

#define PLI pair<LL, int>

#define PII pair<int, int>

#define SZ(x) ((int)x.size())

#define ull unsigned long long

using namespace std;

const int N =  + ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9 + ;

const double eps = 1e-;

int n, cost, a[N], b[N], to[N];

vector<PII> ans;

int main() {

    scanf("%d", &n);

    for(int i = ; i <= n; i++) scanf("%d", &a[i]);

    for(int i = ; i <= n; i++) scanf("%d", &b[i]), to[b[i]] = i;

    for(int i = n; i >= ; i--) {

        if(to[a[i]] > i) {

            int pre = i;

            for(int j = i + ; j <= n && to[a[pre]] != pre; j++) {

                if(to[a[j]] == j) continue;

                ans.push_back(mk(pre, j));

                cost += abs(j - pre);

                swap(a[pre], a[j]);

                pre = j;

            }

        }

    }

    printf("%d\n", cost);

    printf("%d\n", SZ(ans));

    for(auto& t : ans) printf("%d %d\n", t.fi, t.se);

    return ;

}

/*

*/

相关文章