给我生成一个c++贪心算法吧

好的，以下是一个简单的 C++ 贪心算法示例，用于解决一些最小化或最大化问题：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }

    sort(nums.begin(), nums.end()); // 将数组排序

    int sum = 0;
    for (int i = 0; i < n - 1; i++) { // 求相邻两元素之差的和
        sum += nums[i + 1] - nums[i];
    }

    cout << sum << endl;
    return 0;
}

该算法使用了贪心策略，在求解相邻两元素之差的和时，每次选择相邻两个数中的最小值，以尽可能地减小总和。

相关问题

贪心算法最小生成树kruskal 算法c++

Kruskal's算法是一种用于寻找无向图最小生成树的贪心算法。以下是C++的基本实现步骤[^1]：

1. **初始化**：创建一个空的并查集结构（通常使用数组或哈希表），用来表示每个顶点所属的集合；建立一个优先队列（如`std::priority_queue`），以边的权重作为比较依据。

2. **边的排序**：遍历所有边，将它们按照权重从小到大插入优先队列。

3. **构建树**：从优先队列中取出权重最小的边 `(u, v)`。如果这条边连接的两个顶点 `u` 和 `v` 分属于不同的集合（通过并查集检查），则将这条边添加到最小生成树中，并合并这两个集合。重复此过程，直到树中有 `V - 1` 条边，其中 `V` 是图中的顶点数。

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>

// 并查集辅助结构
class DisjointSet {
public:
    std::unordered_map<int, int> parent;
    void make_set(int x) { parent[x] = x; }
    int find_set(int x) { return parent[x] == x ? x : parent[x] = find_set(parent[x]); }
    bool union_sets(int x, int y) {
        int px = find_set(x), py = find_set(y);
        if (px != py)
            parent[py] = px;
        return px != py;
    }
};

int kruskal(std::vector<std::pair<int, std{int, int>>> edges) {
    DisjointSet ds;
    std::priority_queue<std::pair<int, std::pair<int, int>>, std::vector<std::pair<int, std::pair<int, int>>>, std::greater<std::pair<int, std::pair<int, int>>>> pq;
    
    // 添加边到优先队列
    for (const auto& edge : edges) {
        pq.push(edge);
    }

    int result = 0;
    while (ds.parent.size() != ds.V) {
        int weight = pq.top().first;
        int u = pq.top().second.first;
        int v = pq.top().second.second;
        pq.pop();

        // 如果边不形成环
        if (!ds.union_sets(u, v)) {
            result += weight;
            ds.make_set(u); // 更新树的结构
        }
    }
    return result;
}

int main() {
    std::vector<std::pair<int, std::pair<int, int>>> edges = {{1, {0, 1}}, {2, {0, 2}}, {3, {1, 3}}, {4, {2, 4}}, {5, {3, 5}}}; // 示例边
    int mst = kruskal(edges);
    std::cout << "Minimum spanning tree cost: " << mst << "\n";
    return 0;
}

贪心算法最小生成树c++

贪心算法最小生成树是指在一个加权连通图中，找到一个生成树，使得树的所有边的权值之和最小。C++中可以使用Kruskal算法或Prim算法来实现最小生成树。

Kruskal算法的实现步骤如下：
1. 将所有边按照权重从小到大排序。
2. 初始化一个并查集，每个节点都是一个单独的集合。
3. 从权重最小的边开始，依次将边加入生成树中，如果加入该边不会形成环，则将该边加入生成树中，并将该边的两个节点合并为一个集合。
4. 重复步骤3，直到生成树中包含所有节点。

Prim算法的实现步骤如下：
1. 选择一个起始节点，将该节点加入生成树中。
2. 将与该节点相邻的所有边加入一个优先队列中。
3. 从优先队列中取出权重最小的边，如果该边的另一个节点不在生成树中，则将该边加入生成树中，并将该边的另一个节点加入生成树中。
4. 重复步骤3，直到生成树中包含所有节点。