9.1 贪心算法
455.分发饼干
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
示例 1:
输入: g = [1,2,3], s = [1,1]
输出: 1
解释:
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。
示例 2:
输入: g = [1,2], s = [1,2,3]
输出: 2
解释:
你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.
从贪心的角度考虑，应该按照孩子的胃口从小到大的顺序依次满足每个孩子，且对于每个孩子，应该选择可以满足这个孩子的胃口且尺寸最小的饼干。
int findContentChildren(vector<int> &g, vector<int> &s)
{
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int count = 0;
int m = g.size();
int n = s.size();
for (int i = 0, j = 0; i < m && j < n; i++, j++)
{
while (j < n && g[i] > s[j])
{
j++;
}
if (j < n)
{
count++;
}
}
return count;
}
135.分发糖果
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求，给这些孩子分发糖果：
- 每个孩子至少分配到
1个糖果。 - 相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。
示例 1：
输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。
示例 2：
输入：ratings = [1,2,2]
输出：4
解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。
先从左向右遍历一次，如果右边的孩子分数比左边的高，那么右边的孩子比左边的多一颗糖。
再从右向左遍历一次，如果左边的孩子分数比右边高，那么左边孩子的糖加到比右边孩子多一颗。
int candy(vector<int> &ratings)
{
int n = ratings.size();
vector<int> left(n);
for (int i = 0; i < n; i++)
{
if (i > 0 && ratings[i] > ratings[i - 1])
{
left[i] = left[i - 1] + 1;
}
else
{
left[i] = 1;
}
}
int right = 0, ret = 0;
for (int i = n - 1; i >= 0; i--)
{
if (i < n - 1 && ratings[i] > ratings[i + 1])
{
right++;
}
else
{
right = 1;
}
ret += max(left[i], right);
}
return ret;
}