Codeforces 347 B Fixed Points 题解 - c++编程基础

TOP

Codeforces 347 B Fixed Points 题解

2015-07-20 17:46:39 来源: 作者: 【大中小】浏览:1次

一道很容易出错的简单题。反正我是WA了几次。

主要会出错的地方是，如何记录下标和值的对应关系，然后判断swap之后，两个值就是到位了(fixed points)。如 0 1 4 3 2 6 7 5，如何判断swap2和4之后，2和4就是到位了。我使用新的数列记录了原来数组的值对应到原来数组的下标。直接使用map也是可以的，但是速度就慢了。

这是个简单的逻辑，思维却有点绕，最好举多几个例子。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include
             using namespace std; const int MAX_N = (int) 1E5+1; int arr[MAX_N], a2[MAX_N]; int main() { int n; scanf(%d, &n); for (int i = 0; i < n; i++) { scanf(%d, arr+i); } int ans = 0; for (int i = 0; i < n; i++) { if (i == arr[i]) ans++, a2[i] = -1; else a2[arr[i]] = i; } if (ans == n)//ans 不可能等于 n-1 { printf(%d, ans); return 0; } printf( ); ans++; for (int i = 0; i < n; i++) { if (i != arr[i]) { int j = a2[i];//这里的逻辑需要非常细心，很容易出先头疼的错误 if (a2[j] == i) { ans++; break; } } } printf(%d, ans); return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：Codeforces 107B Basketball Team..	下一篇：uva 1399 - Puzzle(AC自动机)

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: