做百度手机网站点击,广州建设专修学院,福州电商网站建设,广州优化公司哪家好分奖金
知识点栈时间限制: 1s 空间限制: 256MB 限定语言: 不限 题目描述: 公司老板做了一笔大生意#xff0c;想要给每位员工分配一些奖金#xff0c;想通过游戏的方式来决定每个人分多少钱。 按照员工的工号顺序#xff0c;每个人随机抽取一个数字。按照工号的顺序往后排列…分奖金
知识点栈时间限制: 1s 空间限制: 256MB 限定语言: 不限 题目描述: 公司老板做了一笔大生意想要给每位员工分配一些奖金想通过游戏的方式来决定每个人分多少钱。 按照员工的工号顺序每个人随机抽取一个数字。按照工号的顺序往后排列遇到第一个数字比自己数字大的那么前面的员工就可以获得“距离数字差值”的奖金。 如果遇不到比自己数字大的就给自己分配随机数数量的奖金。 例如按照工号顺序的随机数字是: 2,10,3。那么第2个员工的数字10比第1个员工的数字2大 所以第1个员工可以获得1(10-2) 8。第2个员工后面没有比他数字更大的员工 所以他获得他分配的随机数数量的奖金就是10。第3个员工是最后一个员工后面也没有比他更大数字的员工所以他得到的奖金是3. 请帮老板计算一下每位员工最终分到的奖金都是多少钱
输入描述: 第一行n表示员工数量 (包含最后一个老板) 第二是每位员工分配的随机数字 例如 0 2 10 3 输出描述: 最终每位员工分到的奖金数量 例如 8 10 3 补充说明 随机数字不重复员工数量(包含老板)范围110000随机数范围1100000
示例1 输入: 3 2 10 3 输出: 8 10 3
示例2 输入: 6 4 2 10 3 5 6 输出: 12 8 10 2 1 6
解题思路
使用 单调栈 从左往右遍历将当前下标的值与不为空的stack里面存放的下标的值进行比较如果nums[stack.peek()] nums[i] 说明栈顶值要小于当前值计算单调栈里存放下标的领取奖金,然后将当前值入栈依次类推通过这种方式单调栈里下标存放的值是单调递减的
public class My {public static void main(String[] args) {Scanner sc new Scanner(System.in);int len Integer.parseInt(sc.nextLine());String line sc.nextLine();String[] strings line.split( );int[] array Arrays.stream(strings).mapToInt(Integer::parseInt).toArray();DequeInteger stack new ArrayDeque();for (int i 0; i array.length; i) {//如果单调栈不为空 且 当前下标对应的值比栈顶存放的下标对应的值大设置奖金弹出栈顶元素然后继续循环否则跳出while (!stack.isEmpty() (array[i] array[stack.peek()])) {int index stack.peek();//获得“距离*数字差值”的奖金。array[index] (i - index) * (array[i] - array[index]);stack.pop();}//将当前下标入栈stack.push(i);}StringBuilder sb new StringBuilder();for (int i 0; i array.length; i) {if (i ! 0) {sb.append( );}sb.append(array[i]);}System.out.println(sb);}
}
