首页 > 代码库 > UVA 10570 meeting with aliens

UVA 10570 meeting with aliens

#include <map>#include <set>#include <list>#include <cmath>#include <ctime>#include <deque>#include <stack>#include <queue>#include <cctype>#include <cstdio>#include <string>#include <vector>#include <climits>#include <cstdlib>#include <cstring>#include <iostream>#include <algorithm>#define LL long long#define PI 3.1415926535897932626using namespace std;int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}#define MAXN 1010int a[MAXN],b[MAXN];int N;int main(){    while (scanf("%d",&N)!=EOF)    {        if (N == 0) break ;        for (int i = 1; i <= N; i++) scanf("%d", &a[i]),a[i+N] = a[i];        int ans = INT_MAX;        for (int i = 1; i <= N; i++)        {            int tmp = 0;            memcpy(b,a,sizeof(a));            for (int j = 1; j <= N; j++)            {                int x = i + j - 1;                if (b[x] != j)                {                    tmp ++;                    int t = b[x];                    b[x] = j;                    for (int k = x + 1; k < i + N ; k++)                        if (b[k] == j)                    {                        b[k] = t;                        break;                    }                }            }            ans = min (ans, tmp);            tmp = 0 ;            memcpy(b,a,sizeof(a));            for (int j = N; j >= 1 && tmp < ans; j--)            {                int x = i + N - j;                if (b[x] != j)                {                    tmp ++ ;                    int t = b[x];                    b[x] = j;                    for (int k = x + 1; k < i + N; k++)                        if (b[k] == j)                    {                        b[k] = t;                        break;                    }                }            }            ans = min (ans,tmp);        }        printf("%d\n",ans);    }    return 0;}

 

UVA 10570 meeting with aliens