C 交换座位
时间限制(普通/Java):1000MS/3000MS 运行内存限制:65536KByte
总提交:185 测试通过:61
描述
学号分别为1,2,3,4,5,6,7,8的8位同学随机排成一排，现在想把他们按学号从小到大排序，在排序的时候每次只能其中的2位同学进行换位，请问最少需要几次这样的换位。
输入
输入有多组数据（组数至少20000），每组输入一个含有12345678的字符串。
输出
输出最少所需的交换次数。
样例输入
12345678
12365478
12345786
样例输出
0
1
2
分析：
由于数字只有8个数，所以可以暴力解决。
根据观察：
如果两个数需要对调，那么交换的次数为1；
如果三个数需要对调，那么交换的次数为2；
如果四个数需要对调，那么交换的次数为3；
...
观察可以得出：如果n个数需要对调，那么交换的次数为n-1；
所以我们只要通过搜索找出8个数字中有多少个“小组”。
比如12365487：有1、2、3、654、87 五大组，组员分别为1、1、1、3、2个人 所以交换次数等于0、0、0、2、1；
加起来就是三次。
AC代码如下：
1. #include<stdio.h> 2. #include<string.h> 3. #include<iostream> 4. using namespace std; 5. 6. char a[9]; 7. bool b[9]; 8. int geshu; 9. void dfs(int x){ 10. b[x] = true; 11. geshu++; 12. if (b[a[x] - '0'] == false) 13. dfs(a[x] - '0'); 14. } 15. 16. int main(){ 17. while (gets(a + 1)){ 18. int sum = 0, i, sum2 = 0; 19. memset(b, false, sizeof(b)); 20. for (i = 1; i <= 8; i++){ 21. geshu = 0; 22. if (b[i] == false){ 23. geshu = 0; 24. dfs(i); 25. } 26. if (geshu > 1){ 27. sum += geshu - 1; 28. } 29. } 30. cout << sum << endl; 31. } 32. return 0; 33. } 34.
