135 Candy

题目

135 Candy

题解

题目的要求：N个孩子站成一行，其中每个孩子有一个评分。要求：每个孩子至少要得到一颗糖；评分比相邻孩子高的，得到的糖也要比相邻的孩子多。求满足上述要求的最小发糖数。

因为第一个要求容易满足，所以先满足它，给每个孩子发一颗糖就行了。

对于第二个要求，为了尽量少发糖，可以采取弥补性发糖的策略，即只在不满足要求的情况下发糖。为了最低限度地进行弥补，可以采取如下贪心策略：按照评分从低到高的顺序，逐一对评分高于相邻孩子的孩子进行弥补。这样进行的弥补，都是在最小评分差距的情况下进行的，因此不会发出多余的糖果。

因为检查要求二和弥补操作都需要位置信息，所以要按照评分从低到高的顺序对数组的下标序列进行排序，用排序后的下标序列进行计算。

代码

class Solution {
public:
	template <typename T>
	vector<size_t> sort_indexes(const vector<T> &v) {
		// initialize original index locations
		vector<size_t> idx(v.size());
		iota(idx.begin(), idx.end(), 0);

		// sort indexes based on comparing values in v
		sort(idx.begin(), idx.end(),
			[&v](size_t i1, size_t i2) {return v[i1] < v[i2]; });

		return idx;
	}

	int candy(vector<int>& ratings) {
		vector<size_t> sorted_index = sort_indexes<int>(ratings);

		vector<int> gives = vector<int>(ratings.size(), 1);

		for (size_t i = 0; i < sorted_index.size(); i++)
		{
			int index = sorted_index[i];
			int rate = ratings[index];

			if (index == 0) {
				if (rate > ratings[index + 1]) {
					gives[index] = gives[index + 1] + 1;
				}
			}

			if (index == ratings.size() - 1) {
				if (rate > ratings[index - 1]) {
					gives[index] = gives[index - 1] + 1;
				}
			}

			if (index > 0 && index < ratings.size() - 1) {
				bool gt_left = rate > ratings[index - 1];
				bool gt_right = rate > ratings[index + 1];

				if (gt_left && !gt_right) {
					gives[index] = gives[index - 1] + 1;
				}

				if (!gt_left && gt_right) {
					gives[index] = gives[index + 1] + 1;
				}

				if (gt_left && gt_right) {
					gives[index] = max(gives[index - 1], gives[index + 1]) + 1;
				}
			}
		}

		return accumulate(gives.begin(), gives.end(), 0);
	}
};