LINK

题意：给出1~n数字的排列，求变为递增有序的最小交换次数

思路：水题。数据给的很小怎么搞都可以。由于坐标和数字都是1~n，所以我使用置换群求循环节个数和长度的方法。

/** @Date    : 2017-07-20 14:45:30  * @FileName: LightOJ 1166 贪心 或 置换群 水题.cpp  * @Platform: Windows  * @Author  : Lweleth (SoungEarlf@gmail.com)  * @Link    : https://github.com/  * @Version : $Id$  */#include <bits/stdc++.h>#define LL long long#define PII pair<int ,int>#define MP(x, y) make_pair((x),(y))#define fi first#define se second#define PB(x) push_back((x))#define MMG(x) memset((x), -1,sizeof(x))#define MMF(x) memset((x),0,sizeof(x))#define MMI(x) memset((x), INF, sizeof(x))using namespace std;const int INF = 0x3f3f3f3f;const int N = 1e5+20;const double eps = 1e-8;int vis[N];int a[N];int q[N];int main(){	int T;	cin >> T;	int c = 0;	while(T--)	{		int n;		scanf("%d", &n);		MMF(vis);		for(int i = 1; i <= n; i++)		{			scanf("%d", a + i);			q[a[i]] = i;		}		int ans = 0;		for(int i = 1; i <= n; i++)		{			vis[a[i]] = 1;			int np = q[a[i]];			int cnt = 1;			while(q[np] != np && !vis[np])				cnt++, vis[np] = 1, np = q[np];			ans += cnt - 1;		}		printf("Case %d: %d\n", ++c, ans);	}    return 0;}

LightOJ 1166 Old Sorting 置换群 或 贪心 水题