UVa 11925 - Generating Permutations（构造法）

发表于 分类于 ， Disqus：

给出一个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博客，格式可能有所偏差。 **

相关文章