2023华为od机试C卷【转盘寿司】Python 实现_华为c卷python

目录

题目

思路

Code

题目

寿司店周年庆，正在举办优惠活动回馈新老客户寿司转盘上总共有 n 盘寿司，prices[i] 是第i盘寿司的价格，如果客户选择了第i盘寿司，寿司店免费赠送客户距离第i盘寿司最近的下一盘寿司j，前提是 prices[j] < prices[i]，如果没有满足条件的j，则不赠送寿司。
每个价格的寿司都可无限供应。
输入描述
输入的每一个数字代表每盘寿司的价格，每盘寿司的价格之间使用空格分隔
寿司的盘数 n 范围为: 1<=n <= 500

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

示例1：
输入：

3 15 6 14
输出：

3 21 9 17

思路

1：有点像单调栈的思想。

2：目的就是要找到当前位置的后面的第一个价格小于当前位置的寿司。但是题目中有一个非常恶心的隐藏条件：【寿司转盘】，这就说明这一个闭环的数组。

3：所以我们把原始数据组延长一倍，然后直接用单调栈的模板算法就行了。

4：leetcode 单调栈大全 https://leetcode.cn/tag/monotonic-stack/problemset/

Code

# coding:utf-8
#JSRUN引擎2.0，支持多达30种语言在线运行，全仿真在线交互输入输出。 
import functools
import sys
from collections import Counter, defaultdict
import copy
from itertools import permutations
import re
import math
import sys
from queue import Queue
 
input_str = input()
tmp2 = [int(x) for x in input_str.split(" ")]
count = 0
nums = [0 for i in range(2*len(tmp2))]
for i in range(len(tmp2)):
    nums[i] = tmp2[i]
    nums[i+len(tmp2)] = tmp2[i]
    count += 2
 
res = [0 for i in range(2*len(tmp2))]
stack = []
i=0
while(True):
    if(i>=count):
        #没有比它更小的数字的话，那就不赠送寿司，本身就是实际得到寿司的最大价格
        while (len(stack)>0) :
            next_pos = stack.pop()
            res[next_pos] = nums[next_pos]
        
        output_str= ""
        #输出一半就行了
        for k in range(len(tmp2)):
            output_str += str(res[k]) + " "
        
        print(output_str[0:-1])
        break
    else:
        #单调递减栈，套用下面的模板即可
        #https://blog.csdn.net/qq_39445165/article/details/118467075
        while (len(stack)>0 and nums[stack[-1]] > nums[i]):
            next_pos = stack.pop()
            res[next_pos] = nums[next_pos] + nums[i]
        
        stack.append(i)
    
    i+=1
 
 

【华为od机试真题Python+JS+Java合集】【超值优惠】：Py/JS/Java合集

【华为od机试真题Python】：Python真题题库

【华为od机试真题JavaScript】：JavaScript真题题库

【华为od机试真题Java】：Java真题题库

【华为od机试真题C++】：C++真题题库

【华为od机试真题C语言】：C语言真题题库

【华为od面试手撕代码题库】：面试手撕代码题库

【华为od机试面试交流群：830285880】