刷题笔记合集🔗

分奖金

问题描述

公司老板做了一笔大生意，想要给每位员工分配一些奖金，想通过游戏的方式来决定每个人分多少钱。

按照员工的工号顺序，每个人随机抽取一个数字。

按照工号的顺序往后排列，遇到第一个数字比自己数字大的，那么，前面的员工就可以获得"距离*数字差值"的奖金。

如果遇不到比自己数字大的，就给自己分配随机数数量的奖金。

例如，按照工号顺序的随机数字是：。

那么第 个员工的数字 比第 个员工的数字 大，所以，第 个员工可以获得 的奖金。

第 个员工后面没有比他数字更大的员工，所以，他获得他分配的随机数数量的奖金，就是 。

第 个员工是最后一个员工，后面也没有比他更大数字的员工，所以他得到的奖金是 。

请帮老板计算一下每位员工最终分到的奖金都是多少钱。

输入格式

第一行 表示员工数量（包含最后一个老板）。

第二行是每位员工分配的随机数字。

输出格式

最终每位员工分到的奖金数量。

样例输入

3
2 10 3

样例输出

8 10 3

数据范围

• 员工数量（包含老板）范围
• 随机数范围
• 随机数字不重复

题解

这道题要求计算每位员工分到的奖金，规则是：若员工后面有比自己数字更大的员工，则获得"距离*差值"的奖金；若没有，则获得自己随机数数量的奖金。

问题的核心是找到每个员工后面第一个比自己数字大的员工。这个问题可以有两种解法：

1. 暴力解法：对于每个员工i，遍历i+1到n的所有员工，找到第一个比i大的。时间复杂度为O(n²)。
2. 单调栈解法：使用单调栈以O(n)的复杂度找到每个员工的下一个更大元素。

考虑到员工数量最大可达10000，使用暴力解法可能会在极端测试用例下超时，所以这里介绍单调栈的解法。

单调栈是一种数据结构，栈中的元素保持单调递增或单调递减的顺序。我们可以用它来高效地找到数组中每个元素的下一个更大元素。

算法步骤：

1. 初始化一个空栈stack和一个数组nextGreater，用于存储每个员工的下一个更大元素的索引（-1表示没有）。
2. 从左到右遍历员工数组：
   • 当栈不为空，且当前员工的数字大于栈顶员工的数字时，栈顶元素找到了下一个更大的元素，即当前员工。更新nextGreater并弹出栈顶。
   • 将当前员工入栈。
3. 最后，遍历数组，根据nextGreater计算每个员工的奖金。

这种方法的时间复杂度是O(n)，空间复杂度也是O(n)，对于给定的数据范围是高效的。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 读取输入
n = int(input())
nums = list(map(int, input().split()))

# 使用单调栈计算每个员工的奖金
def calc_bonus(arr):
    """计算每个员工的奖金"""
    # 初始化单调栈和下一个更大元素数组
    stack = []
    next_greater = [-1] * len(arr)
    
    # 使用单调栈查找每个位置的下一个更大元素
    for i in range(len(arr)):
        # 当栈不为空且当前元素大于栈顶元素对应的值时
        while stack and arr[i] > arr[stack[-1]]:
            # 栈顶元素找到了下一个更大元素
            idx = stack.pop()
            next_greater[idx] = i
        # 当前索引入栈
        stack.append(i)
    
    # 计算奖金
    bonus = []
    for i in range(len(arr)):
        if next_greater[i] == -1:
            # 没有下一个更大元素，获得随机数数量的奖金
            bonus.append(arr[i])
        else:
            # 有下一个更大元素，获得距离*差值的奖金
            dist = next_greater[i] - i
            diff = arr[next_greater[i]] - arr[i]
            bonus.append(dist * diff)
    
    return " ".join(map(str, bonus))