网上推广网站,夸克搜索引擎,歌尔股份砍单,计算机网络设计主要学什么目录
题目链接#xff1a;1.买二赠一 - 蓝桥云课 (lanqiao.cn)
题目描述
输入格式
输出格式
样例输入
样例输出
样例说明
思路
队列贪心
代码实现
总结 题目链接#xff1a;1.买二赠一 - 蓝桥云课 (lanqiao.cn) 题目描述 某商场有 N 件商品#xff0c;其中第 i 件…目录
题目链接1.买二赠一 - 蓝桥云课 (lanqiao.cn)
题目描述
输入格式
输出格式
样例输入
样例输出
样例说明
思路
队列贪心
代码实现
总结 题目链接1.买二赠一 - 蓝桥云课 (lanqiao.cn) 题目描述 某商场有 N 件商品其中第 i 件的价格是 Ai。现在该商场正在进行 “买二赠一” 的优惠活动具体规则是 每购买 2 件商品假设其中较便宜的价格是 P如果两件商品价格一样则 P 等于其中一件商品的价格就可以从剩余商品中任选一件价格不超过 P/2的商品免费获得这一件商品。可以通过反复购买 2 件商品来获得多件免费商品但是每件商品只能被购买或免费获得一次。 小明想知道如果要拿下所有商品包含购买和免费获得至少要花费多少钱 输入格式 第一行包含一个整数 N。 第二行包含 N 个整数代表 A1, A2, A3, . . . AN。 输出格式 输出一个整数代表答案。 样例输入 7 1 4 2 8 5 7 1 1 2 样例输出 25 1 样例说明 小明可以先购买价格 4 和 8 的商品免费获得一件价格为 1 的商品再后买价格为 5 和 7 的商品免费获得价格为 2 的商品最后单独购买剩下的一件价格为 1 的商品。总计花费 4 8 5 7 1 25。不存在花费更低的方案。
对于 30% 的数据1 ≤ N ≤ 20。
对于 100% 的数据1 ≤ N ≤ 5 × 1051 ≤ Ai ≤ 109 思路
队列贪心 这题我真的没有爆出来一个用例因为它真的是需要走一步考虑一步的一道题目而且暴力的话并不好操作所以暴力思路在这里真的就是完全骗不到分了。 我们可以使用队列和贪心来解决这个问题。其实一直会有同学有疑惑你的贪心代码在哪里就像动态规划的递推公式一样看不到一个实际上存在的东西啊。看不到是因为贪心这个思路真的就是和你思维的思路是一样的。就比如这道题我们就是要占最大的便宜也就是买最贵的两个东西来获取最大的便宜的价格。 这里的队列是如何使用的或者说是如何工作的呢这里我们使用队列来存储有多少额度的优惠可以使用。然后根据我们现将贵的东西买走那么队列里先进入的一定是较大的优惠力度然后我们在循环之中每次都判断当前商品的价格是否小于或者等于在队列中存储到的已经拥有了的优惠。如果有的话就可以不加这个商品的价格了我们直接进入下一次循环即可。 主循环的详细解释 从价格最高的商品开始向下检查商品因为 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);// 接收整数 nint 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;QueueInteger queue new LinkedListInteger();// 信号位用于判断是否是第二次购买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修改为falseflag false;}else {// 这次是第一次那么下一次就是第二次了将flag修改为trueflag 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结果了。
