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;
}
还不快抢沙发