c++ - 从数组中选择至少两个元素使得它们的 GCD 为 1 且成本最小的问题的解释

Question

在阅读此处问题的解决方案时，我注意到在通过映射（第二次）的迭代过程中，在某些情况下，某些插入是在同一个映射中执行的（“其他”）。在这种情况下，for 循环的行为是什么？迭代是否省略了新的插入？它是否正确？

编辑：这是代码

// C++ implementation of the approach 

#include <bits/stdc++.h> 

using namespace std; 

  

// Function to return the minimum cost required 

int getMinCost(int arr[], int n, int cost[]) 

{ 

  

    // Map to store <gcd, cost> pair where 

    // cost is the cost to get the current gcd 

    map<int, int> mp; 

    mp.clear(); 

    mp[0] = 0; 

  

    for (int i = 0; i < n; i++) { 

        for (auto it : mp) { 

            int gcd = __gcd(arr[i], it.first); 

  

            // If current gcd value already exists in map 

            if (mp.count(gcd) == 1) 

  

                // Update the minimum cost 

                // to get the current gcd 

                mp[gcd] = min(mp[gcd], it.second + cost[i]); 

  

            else

                mp[gcd] = it.second + cost[i]; 

        } 

    } 

  

    // If there can be no sub-set such that 

    // the gcd of all the elements is 1 

    if (mp[1] == 0) 

        return -1; 

    else

        return mp[1]; 

}

标签： c++dictionary

Answer 1

您的问题有两个部分：插入是否将 for 循环中使用的迭代器保留为有效的迭代器，如果是这样，新插入的元素是在地图中更早还是更晚？

插入映射（通过operator[]不会使迭代器无效，因此编译器为第二个 for 循环生成的迭代器在添加新元素后仍然有效。

因为最大公约数总是小于或等于两个数，所以新插入的元素将具有较低的值it.first（因为相等的值不会添加新元素）。因为 astd::map是一个排序容器（通常存储为二叉树），遍历 astd::map将从最低元素开始并工作到最大元素。由于新元素小于 for 循环中的当前元素，因此新元素不会被当前循环处理（尽管它将用于外i循环的下一次迭代）。