[笔试真题]派分糖果

青旅半醒 2023-06-29 05:37 24阅读 0赞

### 题目描述 ###

有N个孩子站成一排，每个孩子有一个分值。给这些孩子派发糖果，需要满足如下需求：  
1、每个孩子至少分到一个糖果  
2、分值更高的孩子比他相邻位的孩子获得更多的糖果  
求至少需要分发多少糖果？

### 输入描述: ###

0,1,0

### 输出描述: ###

### 输入示例: ###

5，4,1，1

### 输出示例: ###

### 思路 ###

从左到右遍历，当前孩子的分值如果比其左边孩子的高，当前孩子的糖果数等于其左边孩子的糖果数加 1；  
从右到左遍历，当前孩子的分值如果比其右边孩子的高，当前孩子的糖果数等于其右边孩子的糖果数加 1 和 自己糖果数的较大值。

### 代码实现 ###

import java.util.Scanner;
    
    /**
     * @author ellen
     * @date 2020-01-10 14:20
     * @description：派分糖果
     */
    public class Main{
        
        public static void main(String[] args) {
        
            Scanner scanner = new Scanner(System.in);
            String s = scanner.nextLine();
            String[] arrStr = s.split(",");
            int[] arr = new int[arrStr.length];
            for (int i = 0; i < arrStr.length; i++) {
        
                arr[i] = (int)arrStr[i].charAt(0) - 48;
            }
            System.out.println(candy(arr));
        }
        private static int candy(int[] candies){
        
            int sum = 0;
            int[] sums = new int[candies.length];
            for (int i = 0; i < sums.length; i++) {
        
                sums[i] = 1;
            }
            // 从左到右遍历，当前孩子的分值如果比其左边孩子的高，当前孩子的糖果数等于其左边孩子的糖果数加 1
            for (int i = 1; i < sums.length; i++) {
        
                if(candies[i] > candies[i - 1]){
        
                    sums[i] = sums[i - 1] + 1;
                }
            }
            // 从右到左遍历，当前孩子的分值如果比其右边孩子的高，当前孩子的糖果数
            // 等于其右边孩子的糖果数加 1 和 自己糖果数的较大值
            for (int i = sums.length - 2; i >= 0; i--) {
        
                if(candies[i] > candies[i + 1]){
        
                    sums[i] = Math.max(sums[i], sums[i + 1] + 1);
                }
            }
            for (int i = 0; i < sums.length; i++) {
        
                sum += sums[i];
            }
            return sum;
        }
    }