习题 8-6 起重机（Crane，ACM/ICPC CERC 2013, UV1611）

本文主要是介绍习题 8-6 起重机（Crane，ACM/ICPC CERC 2013, UV1611），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题链接：https://vjudge.net/problem/UVA-1611
分类：构造法
备注：中级思维题

题解的想法是，对于每个a[i]!=i，如果有j>i&&a[j]=i，则把a[j]的数换到a[i]这里，因为每次遍历从小到大，后面的变化不会影响前面的变化，最多2n次操作即可。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+5;
const int maxl=531445;
int a[maxn],t,n,ans[maxl][2];
bool check(){for(int i=1;i<=n;i++)if(a[i]!=i)return false;return true;
}
void update(int L,int R){int len=(R-L+1)>>1;for(int i=0;i<len;i++)swap(a[L+i],a[L+len+i]);
}
int main(void){//freopen("in.txt","r",stdin);scanf("%d",&t);while(t--){scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);int tot=0;while(!check()){for(int i=1;i<=n;i++){if(a[i]!=i){int pos=i+1;while(pos<=n&&a[pos]!=i)pos++;if(pos<=n){if(2*pos-i-1<=n){update(i,2*pos-i-1);ans[tot][0]=i;ans[tot][1]=2*pos-i-1;}else{int t=(pos-i+1)%2==0?i:i+1;update(t,pos);ans[tot][0]=t;ans[tot][1]=pos;tot++;pos=(pos-t+1)/2+t-1;update(i,2*pos-i-1);ans[tot][0]=i;ans[tot][1]=2*pos-i-1;}tot++;}}}}printf("%d\n",tot);for(int i=0;i<tot;i++)printf("%d %d\n",ans[i][0],ans[i][1]);    }return 0;
}

这篇关于习题 8-6 起重机（Crane，ACM/ICPC CERC 2013, UV1611）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---