大意:N个外星人围成一桌坐下,有序的排列指N在N-1与N+1中间,现在给出一个序列,问至少交换几次可以得到有序的序列。
思路:不管结果如何,我们可以假设最终的序列是以某个外星人为起点的有序序列,既然如此,我们可以构造另一个序列,把原来的外星人长度增加一倍,这样一来,原序列一定是这个构造序列的子序列。然后通过枚举,可以把最小交换次数求出来。继而解决下一个问题:如何求最小的交换次数?我们可以把1与1号位置的交换,2与2号位置的交换,这样求出的序列即是最小的,这个结论可以记住。然后再反过来求一遍即可,因为题目要求是正、反序列。
#include <iostream> #include <cstdlib> #include <cstdio> #include <cstring> #include <string> #include <algorithm> using namespace std; const int MAXN = 510; const int INF = 0x3f3f3f3f; int a[MAXN*2]; int n; int f(int a[], int n) //求最小交换次数 { bool vis[MAXN] = {0}; int c = 0; for(int i = 0; i < n; i++) if(!vis[i]) { c++; for(int x = i; !vis[x]; x = a[x]) vis[x] = 1; } return n-c; } int read_case() { scanf("%d", &n); if(!n) return 0; for(int i = 0; i < n; i++) { scanf("%d", &a[i]); a[i]--; } return 1; } void solve() { int ans = INF; for(int k = 0; k < 2; k++) //正、反两次 { for(int i = 0; i < n; i++) a[n+i] = a[i]; for(int i = 0; i < n; i++) ans = min(ans, f(a+i, n)); //枚举起点 reverse(a, a+n); //取反 } printf("%d\n", ans); } int main() { while(read_case()) { solve(); } return 0; }