OD C卷 - 转盘寿司

转盘寿司 （200）

• 有一个寿司转盘，prices[i]表示第i盘寿司的价格，客户购买了第i盘后，会赠送一个距离i最近的价格小于当前购买价值的寿司j；
• 若没有满足条件的j，则不赠送；

输入描述：
输入寿司的价格，以空格分开；寿司盘数n在【1,500】
输出描述:
用户购买每盘寿司时，实际获取的总价格；

示例1：
输入：
3 15 6 14
输出：
3 21 9 17

思路：

• 循环数组
• true_prices[i] = prices[i] + prices[j]，不存在这样的j时 则prices[j] = 0

 
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
 
 

原文地址：https://blog.csdn.net/weixin_45228198/article/details/140675315

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！