用C++的方式写出贪心算法的三个例子

1. 分配糖果问题

假设有n个小孩和m个糖果，每个小孩有一个评分，每个小孩最少分到一颗糖果，且评分高的小孩比评分低的小孩分到的糖果要多，问最少需要准备多少颗糖果？

贪心策略：先将每个小孩分到一颗糖果，然后从左到右遍历小孩，如果当前小孩评分比前一个小孩高，则将当前小孩分到的糖果数加1，否则不变。

C++代码实现：

int assignCandy(vector<int>& ratings, int n) {
    vector<int> candies(n, 1);  // 每个小孩初始都有一颗糖果
    for (int i = 1; i < n; i++) {
        if (ratings[i] > ratings[i-1]) {
            candies[i] = candies[i-1] + 1;
        }
    }
    for (int i = n-2; i >= 0; i--) {
        if (ratings[i] > ratings[i+1] && candies[i] <= candies[i+1]) {
            candies[i] = candies[i+1] + 1;
        }
    }
    int res = accumulate(candies.begin(), candies.end(), 0);
    return res;
}

2. 区间覆盖问题

假设有n个区间，每个区间的起始点和终止点都已知，现在需要从这些区间中选出尽可能少的区间，使得这些区间的并集覆盖所有的点，问最少需要选择多少个区间？

贪心策略：先将所有区间按照终止点从小到大排序，然后从左到右遍历每个区间，如果当前区间的起始点在上一个区间的终止点之后，则选择该区间。

C++代码实现：

int intervalCover(vector<vector<int>>& intervals, int n) {
    sort(intervals.begin(), intervals.end(), [](auto& a, auto& b) {
        return a[1] < b[1];
    });
    int res = 0, end = INT_MIN;
    for (auto& interval : intervals) {
        if (interval[0] >= end) {
            res++;
            end = interval[1];
        }
    }
    return res;
}

3. 部分背包问题

假设有n个物品，每个物品有一个重量和一个价值，现在有一个容量为C的背包，需要选出若干个物品放入背包中，使得这些物品的重量不超过C，同时价值之和最大，问最大的价值是多少？

贪心策略：将每个物品按照单位重量的价值从大到小排序，然后从前往后依次选物品，如果当前物品的重量小于等于剩余容量，则全部放入背包中，否则只放入部分物品。

C++代码实现：

struct Item {
    int weight, value;
    double unitValue;
    Item(int w, int v) : weight(w), value(v) {
        unitValue = (double)v / w;
    }
};

int partialKnapsack(vector<Item>& items, int n, int capacity) {
    sort(items.begin(), items.end(), [](auto& a, auto& b) {
        return a.unitValue > b.unitValue;
    });
    int res = 0;
    for (auto& item : items) {
        if (capacity >= item.weight) {
            capacity -= item.weight;
            res += item.value;
        } else {
            res += capacity * item.unitValue;
            break;
        }
    }
    return res;
}