uva 10570——Meeting with Aliens

淡淡的烟草味﹌ 2022-08-09 16:34 166阅读 0赞

题意：输入1-n的排列，每次可以交换两个整数。用最少的次数把排列变成1-n的环状序列。

思路：枚举+贪心。依次枚举环上所有的点，正序一遍，倒序一遍，然后贪心求的所需的最小步数（贪心策略是1与1号交换，2与2号交换……）。

code：

#include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <algorithm>
    #include <cstring>
    #include <sstream>
    #include <string>
    #include <vector>
    #include <list>
    #include <queue>
    #include <stack>
    #include <map>
    #include <set>
    #include <bitset>
    
    using namespace std;
    
    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;
    
    const int INF=0x3fffffff;
    const int inf=-INF;
    const int N=1000000;
    const int M=505;
    const int mod=1000000007;
    const double pi=acos(-1.0);
    
    #define cls(x,c) memset(x,c,sizeof(x))
    #define cpy(x,a) memcpy(x,a,sizeof(a))
    #define fr(i,s,n) for (int i=s;i<=n;i++)
    #define lson l,m,rt<<1
    #define rson m+1,r,rt<<1|1
    #define lrt  rt<<1
    #define rrt  rt<<1|1
    #define middle int m=(r+l)>>1
    #define lowbit(x) (x&-x)
    #define pii pair<int,int>
    #define mk make_pair
    #define IN freopen("in.txt","r",stdin);
    #define OUT freopen("out.txt","w",stdout);
    
    int n,vis[M],v[M*2];
    int sol(int *p)
    {
        cls(vis,0);
        int ct=0,k;
        fr (i,1,n)
        {
            if (vis[i]) continue;
            ct++;k=i;
            while (!vis[k]) vis[k]=1,k=p[k];
        }
        return n-ct;
    }
    int  main()
    {
        while (~scanf("%d",&n)&&n)
        {
            fr (i,1,n) scanf("%d",&v[i]);
            int ans=INF;
            fr(i,1,2)
            {
                fr (j,1,n) v[j+n]=v[j];
                fr(j,1,n) ans=min(ans,sol(v+j));
                reverse(v+1,v+1+n);
            }
            printf("%d\n",ans);
        }
    }