华为OD机考算法题：分奖金

题目部分

---

解读与分析

题目解读：

分奖金时，员工先按照员工号排序。每位员工的奖金数与工号更大的员工抽取的数字相关，与工号小的员工没有关系。

此题可翻译成：有一个整形数组，设为 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 之后，输出数组 arr 的内容。

分析与思路：

虽然此题的难度为“难”，解题思路和算法却都非常简单。

我们可以直接从第 0 个元素开始往后遍历，根据题目解读中提到的两种情况，逐一刷新每个元素的值。因为每个元素的最终值只与排在它后面的元素有关，所以一定要从第 0 个元素开始遍历，而不能从最后一个元素 (n - 1) 开始遍历。

在遍历过程中，最坏的情况需遍历 n! 次元素，此算法的时间复杂度 O(n!)；整个遍历过程只使用了原始数据类型变量，且空间与数组长度无关，此算法的空间复杂度为 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;
}

(完)