贪心算法的分糖果问题问题描述报告基于devc++

好的，下面是贪心算法的分糖果问题问题描述的报告。

问题描述：

有 $n$ 个小朋友和 $m$ 颗糖果，每个小朋友有一个贪心指数 $g_i$，表示他对糖果的喜爱程度。我们需要按照以下要求分配糖果：

1. 每个小朋友至少分到一个糖果。
2. 如果一个小朋友的贪心指数比他旁边的小朋友高，那么他应该得到比旁边的小朋友更多的糖果。

目标是最小化所分发的糖果数量。

解决方案：

首先，我们可以为每个小朋友分配一个糖果。这样，每个小朋友都至少有一个糖果了。

接着，我们需要考虑如何分配剩下的糖果。我们从左到右遍历每个小朋友，如果当前小朋友的贪心指数比前一个小朋友高，那么我们让他的糖果数量比前一个小朋友多一颗。否则，我们只给他一颗糖果。

同样的，我们也要从右到左遍历一遍小朋友，如果当前小朋友的贪心指数比后一个小朋友高，那么我们让他的糖果数量比后一个小朋友多一颗。这样，我们就可以满足所有小朋友的要求了。

最后，我们需要统计一下分配出去的糖果数量。这个数量就是所有小朋友糖果数量之和。

时间复杂度：

对所有小朋友进行两次遍历，所以时间复杂度为 $O(n)$。

代码实现：

下面是 C++ 语言的代码实现。

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

using namespace std;

int min_candies(int n, vector<int>& g) {
    // 每个小朋友至少分到一个糖果
    vector<int> candies(n, 1);

    // 左遍历
    for (int i = 1; i < n; i++) {
        if (g[i] > g[i-1]) {
            candies[i] = candies[i-1] + 1;
        }
    }

    // 右遍历
    for (int i = n-2; i >= 0; i--) {
        if (g[i] > g[i+1]) {
            candies[i] = max(candies[i], candies[i+1] + 1);
        }
    }

    // 统计糖果数量
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += candies[i];
    }
    return sum;
}

int main() {
    int n = 5;
    vector<int> g = {1, 2, 3, 2, 1};
    cout << min_candies(n, g) << endl;  // 输出 7
    return 0;
}

测试样例：

我们可以使用以下样例进行测试。

int n = 5;
vector<int> g = {1, 2, 3, 2, 1};
cout << min_candies(n, g) << endl;  // 输出 7

这个样例中，我们有 $5$ 个小朋友，他们的贪心指数分别为 $[1,2,3,2,1]$。根据贪心算法，我们将分配 $[1,2,3,1,1]$ 颗糖果，总共需要 $7$ 颗糖果。