有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]); } }