题面描述

公司老板进行了一笔大生意，决定通过游戏的方式为每位员工分配奖金。具体规则如下：

• 按照员工的工号顺序，每位员工随机抽取一个数字。
• 对于每位员工，按照工号顺序向后查找，找到第一个数字比自己数字大的员工。
  • 如果找到了这样的员工，则当前员工的奖金为“距离 × 数字差值”，其中距离是两个员工工号的差值，数字差值是后一个员工的数字减去当前员工的数字。
  • 如果没有找到比自己数字大的员工，则当前员工的奖金为其抽取的随机数字。

思路

这个问题可以类比为“下一个更大元素”（Next Greater Element）问题。我们需要为每个员工找到其后面第一个比自己数字更大的员工，然后根据规则计算奖金。如果找不到，则奖金为自己抽取的数字。

为了高效地解决这个问题，可以使用栈来记录员工的索引。具体步骤如下：

1. 初始化一个栈，用于存储员工的索引。
2. 从左到右遍历员工列表：
   • 当当前员工的数字大于栈顶员工对应的数字时，说明当前员工是栈顶员工的“下一个更大元素”。计算奖金并将栈顶员工弹出。
   • 重复上述步骤，直到栈为空或当前员工的数字不大于栈顶员工的数字。
   • 将当前员工的索引压入栈中。
3. 遍历结束后，栈中剩余的员工找不到更大的数字，奖金即为其随机数字。

cpp

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

int main(){
    int n;
    // 读取员工数量
    cin >> n;
    vector<int> nums(n);
    // 读取每位员工的随机数字
    for(int &num : nums){
        cin >> num;
    }
    
    // 结果数组，初始化为0
    vector<long long> result(n, 0);
    // 栈存储员工的索引
    stack<int> s;
    
    for(int i = 0; i < n; ++i){
        // 当栈不为空且当前数字大于栈顶员工的数字
        while(!s.empty() && nums[i] > nums[s.top()]){
            int idx = s.top();
            s.pop();
            // 计算距离和数字差值
            long long distance = i - idx;
            long long diff = nums[i] - nums[idx];
            result[idx] = distance * diff;
        }
        // 将当前员工的索引压入栈中
        s.push(i);
    }
    
    // 对于栈中剩余的员工，奖金为其随机数字
    while(!s.empty()){
        int idx = s.top();
        s.pop();
        result[idx] = nums[idx];
    }
    
    // 输出结果
    for(int i = 0; i < n; ++i){
        if(i != 0) cout << ' ';
        cout << result[i];
    }
    cout << endl;
    
    return 0;
}

python

# 读取员工数量
n = int(input())
# 读取每位员工的随机数字
nums = list(map(int, input().split()))

# 结果数组，初始化为0
result = [0] * n
# 栈存储员工的索引
stack = []

for i in range(n):
    # 当栈不为空且当前数字大于栈顶员工的数字
    while stack and nums[i] > nums[stack[-1]]:
        idx = stack.pop()
        distance = i - idx
        diff = nums[i] - nums[idx]
        result[idx] = distance * diff
    # 将当前员工的索引压入栈中
    stack.append(i)

# 对于栈中剩余的员工，奖金为其随机数字
while stack:
    idx = stack.pop()
    result[idx] = nums[idx]

# 输出结果
print(' '.join(map(str, result)))

java

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 读取员工数量
        int n = Integer.parseInt(br.readLine());
        // 读取每位员工的随机数字
        String[] parts = br.readLine().split(" ");
        int[] nums = new int[n];
        for(int i=0;i<n;i++) nums[i] = Integer.parseInt(parts[i]);
        
        // 结果数组，初始化为0
        long[] result = new long[n];
        // 栈存储员工的索引
        Stack<Integer> stack = new Stack<>();
        
        for(int i=0;i<n;i++){
            // 当栈不为空且当前数字大于栈顶员工的数字
            while(!stack.isEmpty() && nums[i] > nums[stack.peek()]){
                int idx = stack.pop();
                long distance = i - idx;
                long diff = nums[i] - nums[idx];
                result[idx] = distance * diff;
            }
            // 将当前员工的索引压入栈中
            stack.push(i);
        }
        
        // 对于栈中剩余的员工，奖金为其随机数字
        while(!stack.isEmpty()){
            int idx = stack.pop();
            result[idx] = nums[idx];
        }
        
        // 输出结果
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<n;i++){
            if(i > 0) sb.append(' ');
            sb.append(result[i]);
        }
        System.out.println(sb.toString());
    }
}

题目内容

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

按照员工的工号顺序，每个人随机抽取一个数字。按照工号的顺序往后排列，遇到第一个数字比自己数字大的，那么，前面的员工就可以获得“距离 $*$ 数字差值”的奖金。如果遇不到比自己数字大的，就给自己分配随机数数量的奖金。

例如，按照工号顺序的随机数字是：$2,10,3$ 。

那么第 $2$ 个员工的数字 $10$ 比第 $1$ 个员工的数字 $2$ 大，所以，第 $1$ 个员工可以获得 $1 *（10-2）= 8$ 。

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

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

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

输入描述

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

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

输出描述

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

注：随机数字不重复，员工数量（包含老板）范围 $1$ ~ $10000$，随机数范围 $1$ ~ $100000$

样例1

输入

3
2 10 3

输出

8 10 3