題目描述
老師想給孩子們分發糖果，有 N 個孩子站成了一條直線，老師會根據每個孩子的表現，預先給他們評分，
你需要按照以下要求，幫助老師給這些孩子分發糖果：
每個孩子至少分配到 1 個糖果，
評分更高的孩子必須比他兩側的鄰位孩子獲得更多的糖果，
那么這樣下來，老師至少需要準備多少顆糖果呢？
示例
輸入：[1,0,2]
輸出：5
思路
貪心思想，兩次遍歷
AC代碼 C++
class Solution {
public:
int candy(vector<int>& ratings) {
//兩次遍歷，貪心
int l = ratings.size();
if(l<2){
return l;
}
vector<int> s(l,1);
for(int i = 1; i < l; ++i){
if(ratings[i] > ratings[i-1]){
s[i] = s[i-1]+1;
}
}
for(int i = l-1; i > 0; --i){
if(ratings[i] < ratings[i-1]){
s[i-1] = max(s[i-1],s[i]+1);
}
}
//accumulate累加求和函式
return accumulate(s.begin() , s.end() , 0);
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/259933.html
標籤：其他
上一篇：CF 1477A. Nezzar and Board
下一篇：PV與PVC