返回目录

题目描述

寿司店周年庆，正在举办优惠活动回馈新老客户。

寿司转盘上总共有 n 盘寿司，prices[i] 是第 i 盘寿司的价格，

如果客户选择了第 i 盘寿司，寿司店免费赠送客户距离第 i 盘寿司最近的下一盘寿司 j，前提是 prices[j] < prices[i]，如果没有满足条件的 j，则不赠送寿司。

每个价格的寿司都可无限供应。

输入描述

输入的每一个数字代表每盘寿司的价格，每盘寿司的价格之间使用空格分隔，例如

3 15 6 14

表示：

• 第 0 盘寿司价格 prices[0] 为 3
• 第 1 盘寿司价格 prices[1] 为 15
• 第 2 盘寿司价格 prices[2] 为 6
• 第 3 盘寿司价格 prices[3] 为 14

寿司的盘数 n 范围为：1 ≤ n ≤ 500

每盘寿司的价格 price 范围为：1 ≤ price ≤ 1000

输出描述

输出享受优惠后的一组数据，每个值表示客户选择第 i 盘寿司时实际得到的寿司的总价格。使用空格进行分隔，

3 21 9 17

示例：

题目解析

本题其实就是要我们求解数组中每个元素的下一个更小值元素，另外数组是循环的，即：如果数组某个元素之后没有比其更小的，那么可以循环到数组头部继续找。

Python算法源码

message = "This is a new variable."


class SomeClass:
    def __init__(self):
        self.data = []

    def add_data(self, item):
        self.data.append(item)


def some_function():
    print("This is a new function.")

# 函数入参类型和个数
def calculate_sum_with_next_smaller(prices):
    # 记录处理后的价格和
    result = []
    result.extend(prices)

    # 创建单调栈，用于存储待比较的元素索引，栈中索引对应的价格将会单调递增
    stack = []

    n = len(prices)

    # 循环两倍长度的数组，确保每个元素都能找到下一个更小的值
    j = 0
    while j < n * 2:
        # prices_j 是当前考虑的价格
        prices_j = prices[j % n]  # 使用 j % n 循环数组

        # 判断栈是否非空并且当前栈顶价格高于考虑的价格
        while len(stack) > 0:
            # prices_i 是栈顶的价格
            i = stack[-1]

            if prices[i] > prices_j:
                # 栈顶价格高于当前考虑的价格，找到了下一个更小的价格
                stack.pop()
                # 将当前考虑的价格与栈顶价格的总和记录在结果中
                result[i] += prices_j
            else:
                # 当前考虑的价格不小于栈顶价格，停止比较
                break

        # 在第一轮循环中添加价格的索引到栈中
        if j < n:
            stack.append(j)

        j += 1

    return " ".join(map(str, result))



def main():
    # 输入获取
    prices = list(map(int, input().split()))

    # 算法调用并打印结果
    print(calculate_sum_with_next_smaller(prices))

    print(message)
    some_function()

if __name__ == "__main__":
    main()

C算法源码

#include <stdio.h>

#define MAX_PRICES_SIZE 500


char* message = "This is a new variable.";


void some_function() {
    printf("This is a new function.\n");
}

// 模拟类的结构体定义
struct SomeClass {
    int data[MAX_PRICES_SIZE];
    int size;
};

// 模拟类的成员函数：向对象添加数据
void add_data(struct SomeClass *obj, int item) {
    obj->data[obj->size++] = item;
}

// 函数参数和类型说明
void calculate_sum_with_next_smaller(int prices[], int prices_size) {
    // 存储计算结果的数组
    int res[MAX_PRICES_SIZE];
    // 复制价格数组到结果数组
    for (int i = 0; i < prices_size; i++) {
        res[i] = prices[i];
    }

    // 单调栈实现找到下一个更小值
    int stack[MAX_PRICES_SIZE];
    int stack_size = 0;

    // 循环两次以确保所有值都能找到下一个更小值
    for (int j = 0; j < prices_size * 2; j++) {
        // 获取压栈元素
        int prices_j = prices[j % prices_size];

        // 栈操作：比较并更新结果数组
        while (stack_size > 0) {
            int i = stack[stack_size - 1];

            if (prices[i] > prices_j) {
                stack_size--;
                res[i] += prices_j;
            } else {
                break;
            }
        }

        // 第一轮循环进行压栈，第二轮仅比较
        if (j < prices_size) {
            stack[stack_size] = j;
            stack_size++;
        }
    }

    // 打印结果数组
    printf("%d", res[0]);
    for (int i = 1; i < prices_size; i++) {
        printf(" %d", res[i]);
    }

    printf("\n");
    printf("%s\n", message);
    some_function();
}

int main() {
    int prices[MAX_PRICES_SIZE];
    int prices_size = 0;

    // 从标准输入读取价格数据
    while (scanf("%d", &prices[prices_size++])) {
        if (getchar() != ' ') break;
    }

    // 调用计算函数
    calculate_sum_with_next_smaller(prices, prices_size);

    return 0;
}

Java算法源码

import java.util.Arrays;
import java.util.Scanner;

public class Main{

   
    static String message = "This is a new variable.";

  
    public static void someFunction() {
        System.out.println("This is a new function.");
    }

    // （在Java中用类来模拟）
    static class SomeClass {
        int[] data;

        SomeClass(int size) {
            data = new int[size];
        }

        // （在Java中用类的方法来模拟）
        public void addData(int index, int value) {
            data[index] = value;
        }
    }

    // 修改后的函数入参类型和个数
    public static int[] calculateWithNextSmaller(int[] prices) {

        int len = prices.length;
        int[] result = new int[len];

        // 因为可以首位相接，所以扩展为 2 倍长度的数组
        int[] newPrices = new int[len * 2];
        for (int i = 0; i < len; i++) {
            newPrices[i] = prices[i];
            newPrices[i + len] = prices[i];
        }

        for (int i = 0; i < len; i++) {
            int child = newPrices[i];
            for (int j = i + 1; j < i + len; j++) {
                if (newPrices[j] < child) {
                    // 遇到小于的值则退出
                    result[i] = newPrices[j];
                    break;
                }
            }
        }

        return result;
    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int[] prices = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        int len = prices.length;

        SomeClass someObj = new SomeClass(len);
        for (int i = 0; i < len; i++) {
            someObj.addData(i, prices[i]);
        }

        int[] discounts = calculateWithNextSmaller(prices);

        for (int i = 0; i < len; i++) {
            System.out.print(prices[i] + discounts[i] + " ");
        }

        System.out.println("\n" + message);
        someFunction();
    }
}