当前位置: 首页 > >

UVa 1611 Crane (思路题)

发布时间:



题目链接:http://vjudge.net/problem/UVA-1611




大意:给出一个1?n的排列,每次可以选择一个偶数区间,交换前一半和后一半。用不超过9^6次操作将其变为1?n的顺序。




思路:


? ? ?要注意紫书上的提示,最多只需要2n次操作。也就是说,对每个数,最多只需要两次操作即可归位。那么,一次就将某数字归位是什么情况呢?假设现在我们要将数字m归位,那么数字m的正确位置就是m,而现在m的位置为p(设p>m),那么一次归位的做法就是我们选择位置m为交换区间的左端点,2*(p-m)作为区间的长度(即位置p恰好是我们所选区间的右半部分的第一个),这样交换过去后数字m就到了位置m。当然,这个操作的前提是交换区间的右端点不大于n。


? ? 若是不满足上述条件,即交换区间右端点大于n了,这时我们可以先进行一次操作将数字m向左移动足够的距离再进行上面的操作。我们当然希望将m向左移动的越多越好,这个做法还是很好实现的,只需从p开始选一个左端点不小于m的最大偶数区间即可。这样一次移动后,便一定可以使用上述操作一将其一次归位。





#include
#include
#include
#include
#include
#include
#include
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define lc rt<<1
#define rc rt<<1|1
using namespace std;
typedef pair P;
const int maxn = 10000 + 5;
int a[maxn],p[maxn],n; //p数组记录各个数的位置
vector

ans;

void SWAP(int l, int r)
{
int m = (l + r) >> 1;
for(int i = 0; i+l <= m; i++) {
int L = l+i, R = m+i+1;
swap(a[L],a[R]);
swap(p[a[L]],p[a[R]]);
}
ans.push_back(P(l,r));
//printf("haha
");
}

int main()
{
int T;
scanf("%d",&T);
while(T--) {
ans.clear();
scanf("%d",&n);
for(int i = 1; i <= n; i++) scanf("%d",a+i), p[a[i]] = i;
for(int i = 1; i <= n; i++) {
if (a[i] == i) continue;
int pos = p[i];
while(a[i] != i) {
if (n-pos +1 >= pos-i) SWAP(i,i+2*(pos-i)-1); //pos-i为左半区间的长度
else {
int len = pos - i + 1;
if (len & 1) SWAP(i+1,pos);
else SWAP(i,pos);
pos -= len/2;
}
}
}
printf("%d
",ans.size());
for(int i = 0; i < ans.size(); ++i)
printf("%d %d
",ans[i].first,ans[i].second);
}
return 0;
}







友情链接: