习题 8-13 外星人聚会（Meeting with Aliens, UVa10570）

本文主要是介绍习题 8-13 外星人聚会（Meeting with Aliens, UVa10570），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题链接：https://vjudge.net/problem/UVA-10570
分类：枚举法
备注：剪枝

O(n^3)也能过，数据比较水，不过加个数组可以优化到O(n^2）

#include<bits/stdc++.h>
using namespace std;
const int maxn=505;
int a[maxn],pos[maxn],b1[maxn],b2[maxn],n;
int solve(int *a,int *pos,int base){int res=0;for(int i=0;i<n;i++){if(a[(base+i)%n]==i)continue;//i的位置不在i，而在pos[i]，那么要把位置pos[i]和位置i的数字交换int t=pos[i];swap(a[(base+i)%n],a[t]);pos[i]=(base+i)%n; pos[a[t]]=t;res++;}return res;
}
int main(void){//freopen("in.txt","r",stdin);while(~scanf("%d",&n)&&n){for(int i=0;i<n;i++){scanf("%d",&a[i]);a[i]--; pos[a[i]]=i;}int ans=n;for(int i=0;i<n;i++){memcpy(b1,a,sizeof(a));memcpy(b2,pos,sizeof(pos));ans=min(ans,solve(b1,b2,i));}reverse(a,a+n);for(int i=0;i<n;i++)pos[a[i]]=i;for(int i=0;i<n;i++){memcpy(b1,a,sizeof(a));memcpy(b2,pos,sizeof(pos));ans=min(ans,solve(b1,b2,i));}printf("%d\n",ans);}return 0;
}

这篇关于习题 8-13 外星人聚会（Meeting with Aliens, UVa10570）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---