首页 > 代码库 > Sicily 1350. Piggy banks 解题报告

Sicily 1350. Piggy banks 解题报告

2024-07-15 00:50:14   219人阅读

题目：1350. Piggy banks

 

思路：

　　首先把每个钥匙的位置存进key_positions[]中，然后从第一个bank开始，用不同的color给它们分组。比如第一个bank的钥匙在第二个bank中，那么可以直接先开第二个，第二个钥匙在第四个bank中，同样可以先开第四个，以此类推，直到某个钥匙出现在前面的同一组的某个bank中则需要打破一个。visited数组初始化为０，然后访问过后标记为颜色的编号。第２１行visited[cur] == color只有找到颜色相同即在同一组的才需要打破多一个，因为如果钥匙在另一个组中，那么解决那个组之后自然可以拿到这个组的钥匙。

　　坑爹的地方是题目只有一组输入，但是测试的时候必须用while(cin >> n)才能AC

 

代码：

 1 #include <iostream> 2 using namespace std; 3  4 const int MAX = 1000001; 5 int visited[MAX], key_positions[MAX]; 6  7 int main() { 8     int n; 9     while (cin >> n) {10         int result = 0, color = 1;11         for (int i = 1; i <= n; ++i) {12             cin >> key_positions[i];13             visited[i] = 0;14         }15         for (int i = 1; i <= n; ++i) {16             if (visited[i] == 0) {17                 int cur = i;18                 while (visited[cur] == 0) {19                     visited[cur] = color;20                     cur = key_positions[cur];21                     if (visited[cur] == color)22                         result++;23                 }24                 color++;25             }26         }27         cout << result << endl;28     }29     return 0;30 }

 


联系
我们