构造+贪心 Codeforces584E Anton and Ira

题意：给你一个1~n的排列s1,和另一个排列s2,要把s1变成s2，只能交换数字，交换数字的代价是两个数字位置之差，求最小代价

思路：首先把题目变换一下，，变成已知原串s3,要变成1,2,3,...,n-1,n的排列的最小代价，，可以通过s1和s2得到s3

之后的操作，就变得十分技巧。首先，我们能发现，如果交换的两个数字，都是朝着各自的位置前进，那么就一定是最优的。那么现在就算有这个思路，复杂度也是O(n^3)，有没有办法能使复杂度降低，，使用一些数据结构当然是可以的，，不过我们这里有更简单的方法。

假如每次我都是取最小的还没有还原的数，然后往前去交换，慢慢的让它还原到原来的位置，那么这样一定是最优的，接下来我们就证明

如果我取的数字是x，现在这个x在p位置上

如果p<x,按照我的步骤，前x-1已经全部还原了，那么我x的位置至少应该是>=x的，所以这种情况是不可能出现的

如果p=x，那么已经还原了，就不需要处理了

那么必然有p>x,再看，因为1~x-1这些数字肯定是已经还原了，那么换句话说，比x小的数字已经全部还原了，现在在x前面的数字个数，就是p-1,那么p-1个数中又有x-1个数字比x小，又因为p-1>=x,p-1-(x-1)>=1,所以，在区间[x,p-1]中间至少会存在一个数字>=p！

所以复杂度就简化到了O(n^2),就在可承受范围内了~

#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define fuck(x) cout<<"["<<x<<"]"
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w+",stdout)
using namespace std;
typedef long long LL;
typedef pair<int, int>PII;

const int MX = 2e3 + 5;

int A[MX], B[MX];
vector<PII>pr;

int main() {
    int n; //FIN;
    while(~scanf("%d", &n)) {
        pr.clear();

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

        int ans = 0;
        while(true) {
            int pos = -1;
            for(int j = 1; j <= n; j++) {
                if(B[j] != j && (pos == -1 || B[j] < B[pos])) {
                    pos = j;
                }
            }
            if(pos == -1) break;

            while(B[pos] != pos) {
                for(int j = pos - 1; j >= 1; j--) {
                    if(B[j] >= pos) {
                        pr.push_back(PII(j, pos));
                        swap(B[pos], B[j]);
                        ans += pos - j;
                        pos = j;
                        break;
                    }
                }
            }
        }

        printf("%d\n%d\n", ans, (int)pr.size());
        for(int i = 0; i < (int)pr.size(); i++) {
            printf("%d %d\n", pr[i].first, pr[i].second);
        }
    }
    return 0;
}

秒客网

构造+贪心 Codeforces584E Anton and Ira

相关文章