有N个孩子站成一排,每个孩子有一个分值。给这些孩子派发糖果,需要满足如下需求:
1、每个孩子至少分到一个糖果
2、分值更高的孩子比他相邻位的孩子获得更多的糖果
求至少需要分发多少糖果?
/*
左右两次遍历,当 分数较高时,要为他加上糖果
类似于小米的厨师奖金分配题
*/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] str = br.readLine().split(",");
int[] score = new int[str.length];
int[] sweet = new int[str.length];
for(int i = 0;i<str.length;i++){
score[i] = Integer.parseInt(str[i]);
sweet[i]=1;
}
int sum = 0;
//左遍历,分数高,糖果比你多;右边与左边比
for(int i = 1;i<str.length;i++){
if(score[i]>score[i-1]&& sweet[i]<=sweet[i-1])
sweet[i] = sweet[i-1]+1;
}
//右遍历,分数高,糖果取最大的加1;左边与右边比
for(int i = str.length -2;i>=0;i--){
if(score[i]>score[i+1] && sweet[i]<=sweet[i+1])
sweet[i] = Math.max(sweet[i],sweet[i+1])+1;
sum+=sweet[i];
}
System.out.println(sum+sweet[str.length-1]);
}
}