UVa 11925 - Generating Permutations(构造法)

给出一个1到n的排列,给出操作顺序,使升序排列能变为所给排列。

书上的表述又出错了,导致WA了一次。倒着从所给排列变回升序排列,然后倒着打印解。当前两个已经是升序,就把最后一个拿到前面,否则交换之后再拿。

感觉只要不是求最少步解的题,都可以用构造法转化成类似方法求解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int n;
vector<int> a,ans;
int main(){
while(~scanf("%d",&n)&&n){
a.clear(),ans.clear();
for(int i=0;i<n;++i){
int k;
scanf("%d",&k);
a.push_back(k);
}
while(1){
if(a[0]==1){
bool ok=true;
for(int i=0;i<n;++i)
if(a[i]!=i+1){ok=false;break;}
if(ok) break;
}
if(a[0]<a[1]||(a[1]==1&&a[0]==n)){//注意有特例。
ans.push_back(2);
a.insert(a.begin(),a[n-1]);
a.erase(a.end()-1);
}
else{
ans.push_back(1);
swap(a[0],a[1]);
}
}
for(int i=(int)ans.size()-1;i>=0;--i)
printf("%d",ans[i]);
printf("\n");
}
return 0;
}

本文迁移自我的 CSDN博客 ,格式可能有所偏差。