做影视网站违法,大连seo排名外包,网页设计html代码大全下载,图片设计软件appOD统一考试#xff08;C卷#xff09; 分值#xff1a; 100分 题解#xff1a; Java / Python / C 题目描述
寿司店周年庆#xff0c;正在举办优惠活动回馈新老用户。
寿司转盘上总共有 n 盘寿司#xff0c; prices[i] 是第 i 盘寿司的价格。
如果客户选择了第 i 盘寿… OD统一考试C卷 分值 100分 题解 Java / Python / C 题目描述
寿司店周年庆正在举办优惠活动回馈新老用户。
寿司转盘上总共有 n 盘寿司 prices[i] 是第 i 盘寿司的价格。
如果客户选择了第 i 盘寿司 寿司店免费赠送客户距离第 i 盘寿司最近的下一盘寿司 j 前提是 prices[j] prices[i]如果没有满足条件的 i 则不赠送寿司。
每个价格的寿司都可无限供应。
输入描述
输入的每一个数字代表寿司的价格每盘寿司的价格之间使用空格分隔例如
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示例1
输入
3 15 6 14输出
3 21 9 17题解 单调栈是一种特殊的栈数据结构用于解决一类与找下一个更大或更小元素相关的问题。 在这个问题中我们使用单调递减栈。 单调栈的基本思想是维护一个栈使得栈内的元素保持单调递减或单调递增。当新元素要入栈时我们需要弹出栈内所有比该元素小的元素以确保栈的单调性。这样在栈中每个元素的下一个更小或更大的元素就是它本身。 在这个问题中我们用单调递减栈来维护右边第一个价格比当前寿司价格小的寿司位置。算法的步骤如下 初始化一个空栈 st 和一个数组 gift其中 gift[i] 表示免费赠送寿司价格默认为 0。从左到右遍历两倍的寿司列表记当前索引为 idx。如果栈 st 不为空且当前寿司价格 prices[idx] 小于栈顶寿司价格 prices[st.top()]则出栈维护免费赠送寿司价格。将当前索引 idx 入栈。遍历结束后gift[i] 就是每盘寿司实际免费得到赠送寿司的价格。然后打印输出每盘寿司实际得到的寿司的总价格即可。 Java
import java.util.*;/*** author code5bug*/
public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);ListInteger prices new ArrayList();while (scanner.hasNextInt()) {prices.add(scanner.nextInt());}int n prices.size();// gift[i] 表示免费赠送寿司价格int[] gift new int[n];// 大顶栈DequeInteger st new ArrayDequeInteger();for (int i 0; i 2 * n; i) {int idx i % n;// 当前价格小于栈顶价格时则出栈 并维护免费赠送寿司价格while (!st.isEmpty() prices.get(st.peek()) prices.get(idx)) {int popIdx st.pop();if (gift[popIdx] 0) {gift[popIdx] prices.get(idx);}}st.push(idx);}for (int i 0; i n; i) {System.out.print((prices.get(i) gift[i]) );}}
}
Python
from collections import dequeprices list(map(int, input().split()))
n len(prices)# gift[i] 表示免费赠送寿司价格
gift [0] * n
# 大顶栈
st deque()
for i in range(2 * n):idx i % n# 当前价格小于栈顶价格时则出栈 并维护免费赠送寿司价格while st and prices[st[-1]] prices[idx]:pop_idx st.pop()if gift[pop_idx] 0:gift[pop_idx] prices[idx]st.append(idx)for i in range(n):print(prices[i] gift[i], end )
C
#include iostream
#include vector
#include stackusing namespace std;int main() {vectorint prices;int price;while(cin price) {prices.push_back(price);}int n prices.size();// gift[i] 表示免费赠送寿司价格vectorint gift(n, 0);// 大顶栈stackint st;for(int i 0; i 2 * n; i) {int idx i % n;// 当前价格小于栈顶价格时则出栈 并维护免费赠送寿司价格while(!st.empty() prices[st.top()] prices[idx]) {int pop_idx st.top();if(gift[pop_idx] 0) {gift[pop_idx] prices[idx];}st.pop();}st.push(idx);}for(int i 0; i n; i) {cout prices[i] gift[i] ;}return 0;
}
相关练习题
题号题目难度难易度LeetCode 907907. 子数组的最小值之和中等1976LeetCode 768768. 最多能完成排序的块 II困难1788 ❤️华为OD机试面试交流群每日真题分享 加V时备注“华为od加群” 整理题解不易 如果有帮助到您请给点个赞 ❤️ 和收藏 ⭐让更多的人看到。
