UVALive 6588 Crane(思维+贪心)解题报告

2017-02-23 251 次浏览 解题报告

Also available: UVALive 6588, UVA 1611, Gym 100299C

题意

给出 n 个数,每次可以选一个偶数长度的区间,将区间前半部分和后半部分的元素交换。要求最终交换成 1, 2, 3, ..., n 的排列,输出交换步骤,且总次数要小于 531441。

解题思路

我们可以遍历 1 到 n,把数字逐个交换到指定位置。

观察交换规则可以发现,如果当前的目标数字 i 在 pos 位置,我们可以在 [i, n] 这段剩余的乱序区间中尝试划分一个区间,前半部分为 [i, pos-1],后半部分从 pos 开始,长度和前半部分相等。如果我们能在剩余乱序区间内划分出这样一个区间,我们就可以通过一次交换将数字 i 从 pos 位置换到 i 位置。

而如果剩余区间长度不足以划分,则以 pos 位置为右端点,在剩余区间里划分一个尽量长的区间,先进行一次交换,之后再按前面的方法进行一次交换即可。也就是说,每个数最多需要 2 次交换。

参考代码

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

int t, n, a[10001];
vector<pair<int, int> > v;

int Find(int idx) { // 寻找数的位置
    for(int i=1; i<=n; ++i) {
        if(a[i] == idx) return i;
    }

    return 0;
}

void Swap(int s, int e) { // 在 [s, e] 内交换
    int len = e-s+1;
    for(int i=0; i<len/2; ++i) {
        swap(a[s+i], a[s+i+len/2]);
    }
    v.push_back(make_pair(s, e)); // 记录步骤
}

int main(int argc, char const *argv[]) {
    
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        for(int i=1; i<=n; ++i) {
            scanf("%d", &a[i]);
        }
        v.clear();
        for(int i=1; i<=n; ++i) {
            if(a[i] == i) continue;
            int pos = Find(i);
            int end = i+(pos-i)*2-1; // 计算要划分的区间的右端点
            if(end > n) { // 如果长度不够划分
                int len = pos-i+1;
                if(len % 2) Swap(i+1, pos);
                else Swap(i, pos);
                pos = Find(i);
                end = i+(pos-i)*2-1;
            }
            Swap(i, end);
        }
        printf("%lu\n", v.size());
        for(int i=0; i<v.size(); ++i) {
            printf("%d %d\n", v[i].first, v[i].second);
        }
    }
    
    return 0;
}

bLue 创作,采用 知识共享署名 3.0,可自由转载、引用,但需署名作者且注明文章出处。
本文地址:https://dreamer.blue/blog/post/2017/02/23/uvalive-6588.dream

还不快抢沙发

添加新评论