HDU 4985-Little Pony and Permutation（模拟置换）

心已赠人 2022-09-30 09:36 87阅读 0赞

# Little Pony and Permutation #

##### Time Limit : 2000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other) #####

##### Total Submission(s) : 37 Accepted Submission(s) : 14 #####

Problem Description

![C531-1001-1.png][]  
As a unicorn, the ability of using magic is the distinguishing feature among other kind of pony. Being familiar with composition and decomposition is the fundamental course for a young unicorn. Twilight Sparkle is interested in the decomposition of permutations. A permutation of a set S = \{1, 2, ..., n\} is a bijection from S to itself. In the great magician —— Cauchy's two-line notation, one lists the elements of set S in the first row, and then for each element, writes its image under the permutation below it in the second row. For instance, a permutation of set \{1, 2, 3, 4, 5\} σ can be written as:  
  
![4948-1.jpg][]  
Here σ(1) = 2, σ(2) = 5, σ(3) = 4, σ(4) = 3, and σ(5) = 1.  
Twilight Sparkle is going to decompose the permutation into some disjoint cycles. For instance, the above permutation can be rewritten as:  
  
![4948-2.jpg][]  
Help Twilight Sparkle find the **lexicographic smallest solution. (Only considering numbers).**

Input

Input contains multiple test cases (less than 10). For each test case, the first line contains one number n (1<=n<=10^5). The second line contains n numbers which the i-th of them(start from 1) is σ(i).

Output

For each case, output the corresponding result.

Sample Input

5
    2 5 4 3 1
    3
    1 2 3

Sample Output

(1 2 5)(3 4)
    (1)(2)(3)

Source

BestCoder Round \#7

## 题目意思： ##

有1~N，给出这N个数的置换，判断哪些数是同一范围内的，用括号将同一范围内的数括起来。

## 解题思路： ##

用a\[i\]表示数i的置换数，比如题目给的2 5 4 3 1，表示a\[1\]=2,a\[2\]=5,a\[3\]=4,a\[4\]=3,a\[5\]=1.  
因为要求字典序的解，所以我们从a\[1\]开始，每次找到a\[i\]表示的数然后标记其是否访问过，

例如a\[1\]=2,a\[2\]=5,a\[5\]=1，此时a\[1\]=2已经访问，所以这1,2,5三个数是同一个范围内的。

#include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<set>
    #include<map>
    #include<cstdlib>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    #define MAXN 100010
    #define INF 0x3f3f3f3f
    int a[MAXN];
    bool vis[MAXN];
    int main()
    {
    #ifdef ONLINE_JUDGE
    #else
        freopen("G:/cbx/read.txt","r",stdin);
        //freopen("G:/cbx/out.txt","w",stdout);
    #endif
        ios::sync_with_stdio(false);
        cin.tie(0);
        int n;
        while(cin>>n)
        {
            memset(vis,false,sizeof(vis));
            for(int i=1; i<=n; ++i)
                cin>>a[i];
            for(int i=1; i<=n; ++i)
            {
                bool s=true,e=true;//前后括号标记
                int cnt=0;
                if(vis[i]) continue;
                while(1)
                {
                    if(!vis[i])//若当前未访问
                    {
                        if(s)//加前括号
                        {
                            cout<<"("<<i;
                            s=false;
                            vis[i]=true;
                            i=a[i];//取指向的下一个数
                        }
                        else
                        {
                            vis[i]=true;
                            cout<<" "<<i;
                            i=a[i];
                        }
                    }
                    if(vis[i]) ++cnt;
                    if(cnt==n)//当前括号内的全部访问完毕
                    {
                        if(e)
                        {
                            cout<<")";//加后括号
                            e=false;
                        }
                        break;
                    }
                }
            }
            cout<<endl;
        }
        return 0;
    }

[C531-1001-1.png]: /images/20220708/cd8264a159cc4c6d8f45ec460694ed73.png
[4948-1.jpg]: /images/20220708/d06f391a9cd9454c9b840d4891d29e8f.png
[4948-2.jpg]: /images/20220708/d26f6ffad2b9455095827f793a784a40.png