UVA_10570
一开始没有理解题目中所说的exchange positions，还以为只有相邻的才能换，后来发现不相邻的也可以换。
第一次AC的时候有点YY的味道，但后来想了一下，确实这么做是可以的。
首先破环为链，那么最后的序列不论是正着还是反着，都会以其中某一个点为起点，于是我们枚举起点和序列的正反，求出最小的exchange即可。在求的时候用贪心的思想，首先把1换到位置1，再把2换到位置2，如此反复下去。
对于贪心思想的证明，后来想了一个粗糙的证明，不知道这么证是否有说服力。
比如我们在安排1的时候，如果不直接把1换到位置1，那么必然应该是先让1和x换一下（或者中间换很多次），再把1换到第1个位置。而我们画一下图就知道，如果把1不停的和别的位置的元素交换，设交换次数为n，那么最终至多安排好n+1个位置，而安排好这n+1个位置的交换策略也一定能通过贪心的策略用n次交换完成（因为我们可以把这n+1个交换过位置的元素看成封闭的，在贪心策略交换其余元素过程中是不会影响到这些元素的）。
当然，如果不直接把1换到位置1而最后至多安排了n个位置的话，就显然不会比贪心策略更优了，因为贪心策略交换n次至少会安排好n个位置。
在进行exchange操作的时候，如果我们之前再用一个数组存下了每个元素在哪个位置的话，就不必花O(n)的时间再去找想找的元素在哪里了，这样可以节省不少时间。
#include<stdio.h>
#include<string.h>
#define MAXD 510
#define INF 0x3fffffff
int a[MAXD], ans[MAXD], g[MAXD], min, N;
int exchange()
{
int i, j, k, cnt = 0;
for(i = 1; i <= N; i ++)
if(ans[i] != i)
{
g[ans[i]] = g[i];
ans[g[i]] = ans[i];
cnt ++;
}
return cnt;
}
void solve()
{
int i, j, k, start, cnt;
for(i = 1; i <= N; i ++)
scanf("%d", &a[i]);
min = INF;
for(start = 1; start <= N; start ++)
{
for(i = 1, j = start; i <= N; i ++, j ++)
{
if(j > N)
j = 1;
ans[i] = a[j];
g[a[j]] = i;
}
cnt = exchange();
if(cnt < min)
min = cnt;
}
for(start = 1; start <= N; start ++)
{
for(i = 1, j = start; i <= N; i ++, j --)
{
if(j == 0)
j = N;
ans[i] = a[j];
g[a[j]] = i;
}
cnt = exchange();
if(cnt < min)
min = cnt;
}
printf("%d\n", min);
}
int main()
{
for(;;)
{
scanf("%d", &N);
if(!N)
break;
solve();
}
return 0;
}