算法题目：班级里面有n名同学从前到后排成一排，且已经得知了这些同学的成绩，其中第i名同学的成绩是ai

题目：班级里面有n名同学从前到后排成一排，且已经得知了这些同学的成绩，其中第i名同学的成绩是a_i。班主任想根据同学们上个阶段的考试成绩来评定发成绩的数量。为了激励同学，发成绩是需要满足如下要求：
1.相邻同学中成绩好的同学的橙子必须更多。若相邻同学成绩一样，则他们分到的数量必须相等。
2.每个同学至少分配一个橙子。
由于预算有限，班主任希望在符合要求的情况下发出尽可能少的橙子。请问，至少需要准备多少橙子呢？
输入格式
第一行是一个不超过10⁶正整数n，表示学生数量。
接下来一行有n个不超过10⁹的非负整数a_i,表示第i个同学的成绩。
输出格式
输出答案，也就是需要至少准备多少个橙子。

这是一个学习群里，别人问的题目。自己做了下，现在把答案整理一下。

• 这道题的要求很明确

  1.每个学生都至少能分到一个橘子。
  2.相邻学生，成绩高者得到的橘子至少比成绩低者多一个。
  3.相邻学生，分数相同则橘子数一样

题目说预算有限，要求分得橘子在满足上述条件的情况下，橘子总数最少。那么这里有几个重要的隐含条件：

1. 非相邻的同学，分数高者得到的橘子不一定更多。
2. 分数最低的同学，得到的橘子数为1。

下面，我举个栗子。可以看到下面这张图，得分最高的同学D（7分），仅分到3个橘子，而同学J（6分）却获得最多的橘子5个。

我们分析出，分数最低的那个人，一定是得到橘子数最少的，且是1。那么我们便可以从这里着手。

• 思路：前提条件，假设输入分数存在一个int数组里面，n为总人数即数组的长度。

  1.先确定分数最低的同学，我们称为A（A的区间[1，n]），分得的橘子数目为1。（根据上述隐含条件2）
  2.在除去A以外的分数里面，找到分数最低的同学，称为B（B的区间[1，n-1]）。
  3.将B同学的分数和她左右两边的同学（分别用X，Y指代）分数做对比。

  • 若B<X && B<Y，则B分得的橘子为1；
  • 若X<B<Y || X>B>Y，则B分得的橘子为X分得橘子数+1（或Y分得橘子数+1）。
  • 若B>X && B>Y，则B分得的橘子数是XY两人当中获得最多的橘子数+1。
  • 若B=X || B=Y，则B分得的橘子和与他分数相同的那个人的橘子数一样。

  4.循环2、3两步，直至全部分配完毕。

可能有人会对思路步骤3的第二、三点两点有疑惑：你怎么知道X或Y分得的橘子数呢？怎么去+1？

这是因为，我们每次都是从最小的分数开始去分橘子，所以在第三步每次做比较的时候，但凡XY中有分数小于B的人，他一定已经分到了橘子。

接下来，直接上代码

package com.study;import java.util.Arrays;
import java.util.Scanner;public class OrangeNum {public static void main(String[] args) {int stu;//学生数量Scanner input = new Scanner(System.in);System.out.println("请输入学生数量:");stu = input.nextInt();Scanner input2 = new Scanner(System.in);System.out.println("请输入学生成绩，用单个空格分开:");String str = input2.nextLine();String[] s = str.split(" ");int[] grade = new int[stu];//存储学生成绩数组int i=0;for(String x:s){grade[i] = Integer.parseInt(x);i++;}/*==========上述代码已经将输入的数据存储起来准备好。下面开始正式的算法============*/int[] distribute = new int[grade.length];//创建一个数组，与分数数组对应，用于存储每个分数的学生获得的橘子数for(int k=0;k<distribute.length;k++){distribute[k]=-1;}int preMin=0;//根据题目意思，分数最小为0int[] temp = Arrays.copyOf(grade, grade.length);//将分数按照升序排序，存到一个新的数组Arrays.sort(temp);int max = temp[temp.length-1];int maxIndex = grade.length-1;while(preMin != max ){//循环结束条件preMin=minNum(preMin,temp);for(int j=0;j<grade.length;j++){if(grade[j]==preMin){//找到在grade数组里面，值为preMin的角标j//确定j的值后，根据分橘子的两条要求，进行判断，最后将值填到distribute数组的对应位置if((j==0 && distribute[1]==-1) || (j==maxIndex && distribute[j-1]==-1) ||(distribute[j-1]==-1 && distribute[j+1]==-1)){distribute[j]=1;}else if(j==0 && distribute[1]!=-1){if(grade[1]==grade[0]){distribute[j]=distribute[1];}distribute[j]=distribute[j+1]+1;}else if((j==maxIndex && distribute[j-1]!=-1) || (distribute[j-1] !=-1 && distribute[j+1]==-1)){if(grade[j]==grade[j-1]){distribute[j]=distribute[j-1];}distribute[j]=distribute[j-1]+1;}else if(distribute[j-1] ==-1 && distribute[j+1]!=-1){if(grade[j+1]==grade[j]){distribute[j]=distribute[j+1];}distribute[j]=distribute[j+1]+1;}else if(distribute[j-1] !=-1 && distribute[j+1]!=-1){if(grade[j-1]==grade[j] && grade[j]==grade[j+1]){distribute[j]=distribute[j+1];}else if(grade[j-1]>grade[j+1]){distribute[j]=distribute[j-1]+1;}else{distribute[j]=distribute[j+1]+1;}}}}}int allNum=0;for(int m:distribute){allNum+=m;}System.out.println("橘子数=="+allNum);System.out.println(Arrays.toString(distribute));}/**@param preMin:上次找到的最小分数*@param arr:按照升序排好的成绩数组* @return：返回比preMin大的最小分数* */    public static int minNum(int preMin,int[] arr){int res=0;for(int i=0;i<arr.length;i++){if(arr[i]>preMin){res =  arr[i];break;}}return res;}}