2023年蓝桥杯省赛——买二赠一

这里的队列是如何使用的，或者说是如何工作的呢？这里我们使用队列来存储有多少额度的优惠可以使用。然后根据我们现将贵的东西买走，那么队列里先进入的一定是较大的优惠力度，然后我们在循环之中每次都判断当前商品的价格是否小于或者等于在队列中存储到的，已经拥有了的优惠。如果有的话就可以不加这个商品的价格了，我们直接进入下一次循环即可。

主循环的详细解释：

从价格最高的商品开始向下检查商品（因为 nums 数组现在是按价格排序的）：

如果队列非空，并且当前商品的价格小于或等于队列头部的元素（即可以免费获取的商品的上限价格），则将队列头部元素弹出，表示已经找到了可以免费获取的商品。
如果当前商品不能免费获取，则需要判断是否应该被视为第二次购买：
- 如果是，将当前商品价格的一半加入队列（表示下一次可以免费获取的商品的价格上限），并且将 flag 设置为 false，表示下一次购买视为第一次购买。
- 如果不是，将 flag 设置为 true，表示下一次购买视为第二次购买。

代码实现



import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		// 接收整数 n
		int n = sc.nextInt();
		// 接收每件商品的价格
		int[] nums = new int[n];
		for(int i = 0; i < n; i++) {
			nums[i] = sc.nextInt();
		}
		sc.close();
		// 将商品的价格从小到大的排序
		Arrays.sort(nums);
		// 定义出我们的pos当做指针，指向操作的商品的索引
		int pos = n - 1;
		Queue<Integer> queue = new LinkedList<Integer>();
		// 信号位，用于判断是否是第二次购买
		boolean flag = false;
		// 初始化结果为0，这里使用long型，因为数据有点大
		long res = 0L;
		
		// 进入贪心的循环之中
		while(pos >= 0) {
			
			// 如果上一轮给的免费额度足够这次的商品的价格
			// 那么将商品弹出即可，不用加入到res中
			if (!queue.isEmpty() && nums[pos] <= queue.peek()) {
				queue.poll();
			}else {
				if (flag) {
					// 是第二次购买则增加免费次数
					queue.add(nums[pos] / 2);
					// 然后使用了免费的次数，再将flag修改为false
					flag = false;
				}else {
					// 这次是第一次，那么下一次就是第二次了，将flag修改为true
					flag = true;
				}
				// 加到结果中
				res += nums[pos];
			}
			pos--;
		}
		System.out.println(res);
	}
}

AC喽喽喽喽喽喽喽喽喽喽喽喽喽喽喽喽喽喽喽喽喽喽喽喽喽喽喽！！！！！！！！！！

总结

其实这道题的思路难就难在呃，斯~~哪里难了。。。。。。。。。。。。。。。。

好吧，其实这里如果被题目迷惑的话，会有难度。

来我们来看这个坑die题目的样例说明，小明可以先购买4和8，然后免费获得价格为1的商品，然后再购买5和7然后获得价格为2的商品。这个其实很难不让人往一种组合的方向上寻找答案，然后找不到便只能是放弃了。但是其实这道题我们可以不着急选赠送给我们的商品，就像这个案例一样。

1 2 2 4 5 7 8

我们直接豪掷千金买下7和8，那么7 / 2 = 3，此时就已经有了一个额度为 3 的免费的“卷”，那么接下来就可以在遇到商品的价格小于等于3的时候直接免费拿下这个商品了，因为我们的从后往前来消费的，所以这里一定是可以免费的商品中最贵的那一个。然后接着循环即可找到最后的res结果了。

标签：队列,样例,蓝桥,商品,购买,买二赠,省赛,价格,免费
From： https://blog.csdn.net/DDDDWJDDDD/article/details/137476479

2023年蓝桥杯省赛——买二赠一

题目链接：1.买二赠一 - 蓝桥云课 (lanqiao.cn)

题目描述

输入格式

输出格式

样例输入

样例输出

样例说明

思路

队列+贪心

代码实现

总结

相关文章

赞助商

阅读排行