题目部分
题目 | 分奖金 |
难度 | 难 |
题目说明 | 公司老板做了一笔大生意,想要给每位员工分配一些奖金,想通过游戏的方式来决定每个人分多少钱。按照员工的工号顺序,每个人随机抽取一个数字。按照工号的顺序往后排列,遇到第一个数字比自己数字大的,那么,前面的员工就可以获得 距离 * 数字差值 的奖金。如果遇不到比自己数字大的,就给自己分配随机数数量的奖金。例如,按照工号顺序的随机数字是:2,10,3。那么第 2 个员工的数字 10 比第 1 个员工的数字 2 大,所以,第 1 个员工可以获得 1 * (10 - 2) = 8。第 2 个员工后面没有比他数字更大的员工,所以,他获得他分配的随机数数量的奖金,就是 10。第 3 个员工是最后一个员工,后面也没有比他更大数字的员工,所以他得到的奖金是 3。 请帮老板计算一下每位员工最终分到的奖金都是多少钱。 |
输入描述 | 第一行 n 表示员工数量(包含最后一个老板)。 第二是每位员工分配的随机数字。 例如: 3 2 10 3 |
输出描述 | 最终每位员工分到的奖金数量。 例如: 8 10 3 |
补充说明 | 随机数字不重复,员工数量(包含老板)范围 1 ~ 10000,随机数范围 1 ~ 100000。 |
------------------------------------------------------ | |
示例 | |
示例1 | |
输入 | 3 2 10 3 |
输出 | 8 10 3 |
说明 | 无 |
解读与分析
题目解读:
此题可翻译成:有一个整形数组,设为 arr,其长度为 n,数组个元素已经初始化为指定的值。对于数组中第 i (0 ≤ i < n)个元素,如果:
1. 在第 ( i + 1 ) 到 n 个元素中存在比 arr[i] 大的元素,如果这样的元素有多个,假设下标最小的元素其下标为 j,那么 arr[i] 的值修改为 ( arr[j] - arr[i] ) * ( j - i)。
2. 在第 ( i + 1 ) 到 n 个元素中存在比 arr[i] 大的元素,那么 arr[i] 的值保持不变。
最后,输出数组 arr 的内容。
分析与思路:
我们可以直接从第 0 个元素开始往后遍历,计算每个元素的值。以为每个元素的值只后排在它后面的元素有关,所以一定要从第 0 个元素开始遍历,而不能从最后一个元素 n - 1 开始遍历。
此方法的时间复杂度 o(),空间复杂度为 o(1)。
代码实现
Java代码
import java.util.Scanner;/*** 分奖金* @since 2023.09.11* @version 0.1* @author Frank**/
public class BonusDistribution {public static void main(String[] args) {Scanner sc = new Scanner(System.in);while (sc.hasNext()) {String input = sc.nextLine();int count = Integer.parseInt( input );input = sc.nextLine();String[] numbers = input.split( " " );// 此处 count == numbers.count,可以完全不用考虑 count.processBonusDistribution( numbers );}}private static void processBonusDistribution( String numbers[] ){int[] arr = arrString2Int( numbers );for( int i = 0; i < arr.length; i ++ ){for( int j = i + 1; j < arr.length; j ++ ){if( arr[j] > arr[i] ){arr[i] = ( arr[j] - arr[i] ) * ( j - i );break;}}}StringBuffer sb = new StringBuffer();for( int i = 0; i < arr.length; i ++ ){if( i != arr.length - 1 ){sb.append( arr[i] + " " );}else{sb.append( arr[i] );}}System.out.println( sb.toString() );}private static int[] arrString2Int( String numbers[] ){int ret[] = new int[numbers.length];for( int i = 0; i < numbers.length; i ++ ){ret[i] = Integer.parseInt( numbers[i] );}return ret;}}
JavaScript代码
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
void async function() {while (line = await readline()) {// count 可以忽略var count = parseInt(line);line = await readline();var numberArr = line.split(" ");processBonusDistribution(numberArr);}
}();function processBonusDistribution(numberArr) {var arr = arrString2Int( numberArr );for( var i = 0; i < arr.length; i ++ ){for( var j = i + 1; j < arr.length; j ++ ){if( arr[j] > arr[i] ){arr[i] = ( arr[j] - arr[i] ) * ( j - i );break;}}}console.log( arr.join(" "));
}function arrString2Int( numberArr )
{var ret = [];for( var i = 0; i < numberArr.length; i ++){ret.push( parseInt( numberArr[i] ) );}return ret;
}
(完)