Candy

發表於   |   分類於

Candy

这个题目在HackerRank上面也有，链接在 这里

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

  • Each child must have at least one candy.
  • Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
public:
	int candy(vector<int>& ratings) {
		vector<int> candies(ratings.size(), 0);
		candies[0] = 1;
		int flag = 0;
		bool less = false;
		for (int i = 1; i < ratings.size(); ++i)
		{
			if (ratings[i] > ratings[i - 1])
			{
				candies[i] = candies[i - 1] + 1;
			}
			else if (ratings[i] < ratings[i - 1])
			{
				flag = i - 1;
				while (i < ratings.size() && ratings[i] < ratings[i - 1])
					++i;
				--i;
				int diff = i - flag; // 判断后面有多少个比flag位置小的数
				if (diff >= candies[flag])
				{
				  // 重新调整分配的糖果
					for (int k = flag; k <= i; ++k)
					{
						candies[k] = diff+1;
						--diff;
					}
				}
				else
				{
					for (int k = flag + 1; k <= i; ++k)
					{
						candies[k] = diff;
						--diff;
					}
				}
			}
			else
			{
				candies[i] = 1;
			}
		}

		int sum = 0;
		for (int i = 0; i < ratings.size(); ++i)
		{
			sum += candies[i];
		}

		return sum;
	}
};