题目链接：http://codeforces.com/problemset/problem/347/B

 

题意：

给你一个 0 ~ n-1 的全排列，可以交换两个数的位置一次，问最多能有多少个数与自己所在的位置对应

 

思路：

注意它给的是0->n-1的全排列，这个非常特别，因为0 的话就应该在0号位置，1就应该在1号位置

所以如果他在正确的位置那么我们就不用管它，如果它不在我们就采取贪心的策略：这个数应该在的那个位置的数应该在的位置是不是就是这个数现在在的位置呢？

如果发现不存在这种完美的策略，那么最后随便换一个就好了

 

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <set>
 6 #include <vector>
 7  
 8 using namespace std;
 9 const int maxn= 1e5 + 10;
10  
11  
12 struct Node{
13     int val;
14     int id;
15 }node[maxn];
16  
17  
18 int main(){
19     int n;
20     scanf("%d",&n);
21     for (int i=0;i<n;i++){
22         scanf("%d",&node[i].val);
23         node[i].id = i;
24     }
25     int cnt = 0;
26     bool flag = true;
27     for (int i=0;i<n;i++){
28         if (node[node[i].val].id == i){
29             cnt++;
30         }
31         if (node[node[i].val].id != i && node[node[node[node[i].val].id].val].id == i && flag){
32             cnt += 2;
33             flag = false;
34         }
35     }
36     if (cnt >= n){
37         printf("%d\n",cnt);
38     }
39     else if (flag)
40         printf("%d\n",++cnt);
41     else
42         printf("%d\n",cnt);
43 }