leetcode || 135、Candy
来源：程序员人生 发布时间：2015-06-09 08:33:16 阅读次数：3290次
problem：
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?
Hide Tags
Greedy
题意： 给小盆友发糖果，属性高的糖果要更多
thinking：
（1）1道简单的贪心题目，为什么通过率这么低？？题目中根本没提属性相等时怎样发糖果。又是1道不严谨的题目。提交发现，
122的小盆友发了4个糖果，说明，第3个小盆友发了1个糖果，换做你是小盆友，你会高兴吗...
（2）撇开相等的情况不说，这道题只要处理好递减的情况就好了。递增或乱序好处理些
code：
class Solution{
public:
int candy(vector<int> &ratings) {
int Total = 0; /// Total candies
int length = 0; /// Continuous descending length of rate
int nPreCanCnt = 1; /// Previous child's candy count
int beforeDenc = nPreCanCnt;
if(ratings.begin() != ratings.end())
{
Total++; //Counting the first child's candy (1).
for(vector<int>::iterator i = ratings.begin()+1; i!= ratings.end(); i++)
{
if(*i < *(i⑴))
{
length++;
if(beforeDenc <= length)
{
Total++;
}
Total += length;
nPreCanCnt = 1; //This step is important, it ensures that once we leave the decending sequence, candy number start from 1
}
else
{
int curCanCnt = 0;
if(*i > *(i⑴))
{
curCanCnt = (nPreCanCnt + 1);
}
else
{
curCanCnt = 1;
}
Total += curCanCnt;
nPreCanCnt = curCanCnt;
length = 0; //reset length of decending sequence
beforeDenc = curCanCnt;
}
}
}
return Total;
}
};
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
