leetCode134:分发糖果

目录

一、题目描述

二、解题思路

三、代码实现


一、题目描述

老师想给孩子们分发糖果,有 N 个孩子站成了一条直线,老师会根据每个孩子的表现,预先给他们评分。

你需要按照以下要求,帮助老师给这些孩子分发糖果:

  • 每个孩子至少分配到 1 个糖果。
  • 相邻的孩子中,评分高的孩子必须获得更多的糖果。

那么这样下来,老师至少需要准备多少颗糖果呢?

示例 1:

输入: [1,0,2]
输出: 5
解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。

示例 2:

输入: [1,2,2]
输出: 4
解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。
     第三个孩子只得到 1 颗糖果,这已满足上述两个条件。

二、解题思路

这道题一开始直觉就是模拟,初始每人一颗,然后根据左边与右边的情况来增加数量;增加的策略是只有比左边多才加一,比右边多也加一,所有这题是贪心算法。

局部最优是比左边多加一,比右边多也加一;全局最优是糖果数最少;局部最优可以得到全局最优。

细节:

如果一遍遍历中对左右两边去操作,得到的结果不一定对。比如ratings={1,2,6,6,6,2,1},得到的糖果情况会是candies={1,2,3,1,2,2,1},而正确的结果是candies={1,2,3,1,3,2,1}。

这是因为在计算第三个6(ratings[4])时,6(ratings[4])不比左边6(ratings[3])大,糖果数不加一;比右边2(ratings[5])大,糖果数加一得到2。

错误的点在于右边的2(ratings[5])的糖果数并不正确,因为他比他右边的1(ratings[6])大,6的糖果数应该在2的糖果数的基础上加一,才能得到正确的结果。

正确的做法是:两边遍历(先从左往右,在从右往左,调换顺序也一样)

左->右:满足右边规则,右边更大的评分得到更多的糖果;

右->左:满足左边规则,左边更大的评分得到更多的糖果;

三、代码实现

#include <bits/stdc++.h>
using namespace std;
int candy(vector<int>& ratings) {
	int length = ratings.size();
	vector<int> candies(length, 1);
	for (int j = 0; j < length; j++) {
		if (j > 0 && ratings[j] > ratings[j - 1]) {
			candies[j] = candies[j - 1] + 1;
		}
	}
	for (int j = length - 1; j >= 0; j--) {
		if (j < length - 1 && ratings[j] > ratings[j + 1] && candies[j] <= candies[j + 1]) {
			candies[j] = candies[j + 1] + 1;
		}
	}
	int res = 0;
	for (int i = 0; i < length; i++) {
		res += candies[i];
	}
	return res;
}
int main() {
	vector<int> ratings = { 1,3,4,5,2 };
	cout << candy(ratings);
	return 0;
}

 

上一篇:AtCoder Regular Contest 121 D - 1 or 2


下一篇:Codeforces Round #683 (Div. 2) Problem - A.Add Candies 题解