习题 8-7 生成排列（Generating Permutations，UVa11925）

本文主要是介绍习题 8-7 生成排列（Generating Permutations，UVa11925），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

给一个数字n，和一个长度为n的排列，求如何操作使得1,2,…,n变成给定的排列。操作1为把前两个数交换位置，操作2为把第一个数放到最后。
逆向操作，即把操作2改为把最后一个数放到前面，从给定的序列变成1,2,…,n的序列。
按照一般想法，小的数在大的数前面，如果前两个数，前者更大则要交换位置，否则把尾部的数放到头部，除非第一个数是n的时候不换位置，不然可能死循环。

#include<bits/stdc++.h>
using namespace std;
const int maxn=305;
int n,a[maxn],ans[maxn*1000];
bool check(int n,int base){for(int i=0;i<n;i++)if(a[(base+i)%n]!=i+1)return false;return true;
}
int main(void){//freopen("in.txt","r",stdin);while(~scanf("%d",&n)&&n){for(int i=0;i<n;i++)scanf("%d",&a[i]);int base=0,tot=0;while(!check(n,base)){if(a[base]>a[(base+1)%n]&&a[base]!=n){ans[tot++]=1;swap(a[base],a[(base+1)%n]);}else{base=(base+n-1)%n;ans[tot++]=2;}}for(int i=tot-1;i>=0;i--)printf("%d",ans[i]);printf("\n");}return 0;
}

这篇关于习题 8-7 生成排列（Generating Permutations，UVa11925）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---