阿里测评题

成绩高的孩子会比成绩弱的孩子得到的小贴纸多,请问需要多少小贴纸发给孩子们?

Posted by coding-zen on August 3, 2018
题目:

现在很多家长都会送小孩子去培训中心学习舞蹈,有一次舞蹈培训中心考试,因为小孩子要哄着才能更喜欢学,所以老师给孩子们准备了小贴纸奖励孩子,考试结束以后孩子们按照大小个站成一排,老师按照顺序给孩子们发小贴纸,每个孩子都会至少得到一个小贴纸,因为是按照大小个站成一排的,所以相邻的孩子成绩略有高低,为了鼓励相邻孩子向成绩好的孩子学习,成绩高的孩子会比成绩弱的孩子得到的小贴纸多,请问需要多少小贴纸发给孩子们?

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();//读入一行string
        String[] c = s.split(",");//根据“,”进行分割
        int[] arr = new int[c.length];
        for (int i = 0; i < c.length; i++) {
            arr[i] = Integer.parseInt(c[i]);//将string转为int型
        }

        int [] paper=new int[arr.length];//定义分配贴纸的数组

        Arrays.fill(paper,1);//初始化为1

        for(int i=0;i<arr.length;i++){

            //前一个比当前的小,当前加1
            if(i!=0){
                if(arr[i]>arr[i-1])
                    paper[i]=paper[i-1]+1;
                else if(arr[i]==arr[i-1])
                    paper[i]=paper[i-1];
            }

            //一个往前比,一个往后比,这个难想

            //后一个比当前的小,当前加1
            if(i!=arr.length-1&&arr[i]>arr[i+1]){
                paper[i]=paper[i+1]+1;
                //加1后,如果前一个和当前相等,则前一个继续加1,向前遍历
                for(int j=i;paper[j-1]==paper[j];j--){
                    paper[j-1]=paper[j]+1;
                }
            }

        }

        //输出总数
        int sum=0;

        for(int i=0;i<arr.length;i++){
            sum+=paper[i];
            System.out.println(paper[i]);
        }

        System.out.println(sum);

    }
}