UVA - 10570 Meeting with Aliens - c++编程基础

题目大意：N个外星人围成一桌坐下，有序的排列指N在N-1与N+1中间，现在给出一个序列，问至少交换几次可以得到有序的序列。

解题思路：不管结果如何，我们可以假设最终的序列是以某个外星人为起点的有序序列，既然如此，我们可以构造另一个序列，把原来的外星人长度增加一倍，这样一来，原序列一定是这个构造序列的子序列。然后通过枚举，可以把最小交换次数求出来。继而解决下一个问题：如何求最小的交换次数？我们可以把1与1号位置的交换，2与2号位置的交换，这样求出的序列即是最小的，这个结论可以记住。然后再反过来求一遍即可，因为题目要求是正、反序列。
?

#include 
   
     #include 
    
      using namespace std; int cal(int A[], int N) { int cnt = 0, vis[505] = {0}; for (int i = 1; i <= N; i++) if(!vis[i]) { cnt++; for (int j = i; !vis[j]; j = A[j]) vis[j] = 1; } return N - cnt; } int main() { int N, A[1010], B[1010]; while (scanf("%d", &N), N) { for (int i = 1; i <= N; i++) { scanf("%d", &A[i]); B[N - i + 1] = B[2 * N - i + 1] = A[i + N] = A[i]; } int ans = 1 << 30; for (int i = 0; i < N; i++) ans = min(ans, cal(A + i, N)); for (int i = 0; i < N; i++) ans = min(ans, cal(B + i, N)); printf("%d\n", ans); } return 0; }