首页 > 试题广场 >

派分糖果

[编程题]派分糖果
  • 热度指数:2551 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

N个孩子站成一排,每个孩子有一个分值。给这些孩子派发糖果,需要满足如下需求:

1、每个孩子至少分到一个糖果

2、分值更高的孩子比他相邻位的孩子获得更多的糖果

求至少需要分发多少糖果?


输入描述:
0,1,0


输出描述:
4
示例1

输入

5,4,1,1

输出

7
/*
左右两次遍历,当 分数较高时,要为他加上糖果
类似于小米的厨师奖金分配题
*/
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]);
    }
}

发表于 2020-05-17 11:41:07 回复(2)