当前位置：首页 > news >正文

UVA10570 Meeting with Aliens（枚举/优化）

news 来源：原创 2024/5/10 12:13:02

题目链接

在这里插入图片描述
1.题目大意：输入一个1-n的排列，每次可以交换任意位置的两个数，求最少将排列变成1-n的一个环状序列的交换次数

2.这个题目找不到什么规律的，也就是没有可行的算法解决，那么只能采用暴力解法，枚举每个数字开头的环状序列。简单模拟一下，不难发现每个数对应的环状序列都有两种，而且排列都可以分成两个部分，对于数字k开头的环状序列有以下两种：

{k,k+1,…,n} + {1,2,…,k-1}
{k,k-1,…,1} + {n,n-1,…,k+1}
那么我们只需算出每个数字的两种情况即可，时间复杂度O(n²)

3.这里用到了一些函数和技巧，比如观察上面的两个序列，第一个是由k开始一直加一直到越界后再变为1再逐渐加一，第二个是每次减一直到越界变为n再继续减一，那么我们一个函数就能完成两个序列的计算，很巧妙。我自己写了一大堆乱套了。还有就是"memcpy(目标数组,源数组,sizeof 源数组)"——数组赋值的使用

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=505;
int n;
int a[maxn],b[maxn],pos[maxn],p[maxn];

int solve(int x,int d){
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(b[i]!=x){
            cnt++;
            b[p[x]]=b[i];
            p[b[i]]=p[x];
            b[i]=x;
            p[x]=i;
        }
        x+=d;
        if(x>n) x=1;
        if(x<=0) x=n;
    }
    return cnt;
}

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    while(cin>>n && n){
        for(int i=1;i<=n;i++){
            cin>>a[i];
            pos[a[i]]=i;
        }
        int ans=inf;
        for(int i=1;i<=n;i++){
            memcpy(b,a,sizeof a);
            memcpy(p,pos,sizeof pos);
            ans=min(ans,solve(i,-1));
            memcpy(b,a,sizeof a);
            memcpy(p,pos,sizeof pos);
            ans=min(ans,solve(i,1));
        }
        cout<<ans<<endl;
    }
    return 0;
}