当前位置：首页 > news >正文

[23年蓝桥杯] 买二赠一

news 2025/8/18 0:26:08

题目描述

【问题描述】
某商场有 N 件商品，其中第 i 件的价格是 A i 。现在该商场正在进行 “ 买二赠一” 的优惠活动，具体规则是：每购买 2 件商品，假设其中较便宜的价格是 P （如果两件商品价格一样，
则 P 等于其中一件商品的价格），就可以从剩余商品中任选一件价格不超过 P /2 的商品，免费获得这一件商品。可以通过反复购买 2 件商品来获得多件免费商品，但是每件商品只能被购买或免费获得一次。小明想知道如果要拿下所有商品（包含购买和免费获得），至少要花费多少钱？
【输入格式】
第一行包含一个整数 N 。
第二行包含 N 个整数，代表 A 1 , A 2 , A 3 , . . . ， A N
【输出格式】
输出一个整数，代表答案。
【样例输入】

7
1 4 2 8 5 7 1

【样例输出】

【样例说明】

小明可以先购买价格 4 和 8 的商品，免费获得一件价格为 1 的商品；再后
买价格为 5 和 7 的商品，免费获得价格为 2 的商品；最后单独购买剩下的一件
价格为 1 的商品。总计花费 4 + 8 + 5 + 7 + 1 = 25 。不存在花费更低的方案。
【评测用例规模与约定】
对于 30 % 的数据， 1 ≤ N ≤ 20 。
对于 100 % 的数据， 1 ≤ N ≤ 5 × 10⁵ ，1 ≤ A i ≤ 10⁹ 。

思路

要尽可能使送的金额大
所以排序后从后往前遍历, 再到后面找有没有符合条件的两个金额

破题点在找到后面的符合条件的金额

因为送的金额要尽可能大, 所以买的金额也要大
所以从后面找金额的时候, 要优先找大的且没用过的,
一种想法是用队列来保存

思路是
遍历的时候把当前元素值的两倍与队列中倒数第二个数比较 (如果队列中少于两个元素就加入队列)
符合条件就把队列中最大的两个数弹出
不符合条件就就将其加入队列

如此直到遍历完为止

细节处理

怎么看到队列中第二个元素

因为不能直接看到队列倒数第二元素, 所以在测试之间就把队列前两个元素弹出, 再用一个标志位了模拟其是否弹出
这样的队列 + 维护的两个变量 + 一个标志位就相当于模拟了原来的队列了
因为我们只需要与较小的比, 所以只需要维护一个变量即可

怎么算总金额

一种比较便捷的方式是, 假设不优惠全买了
再按优惠来退钱

所以再遍历输入的时候, 算总金额, 在找到可以优惠的时候, 减去优惠金额即可

贴个代码

import java.util.*;  /**  * @author Fancier  * @version 1.0  * @description: ThreeForTwo  * @date 2024/4/8 22:15  */  
public class Main {  public static void main(String[] args) {  Scanner cin = new Scanner(System.in);  int n = cin.nextInt(), cnt = n / 3;  long[] arr = new long[n];  long sum = 0;  for (int i = 0; i < n; i++) {  arr[i] = cin.nextInt();  sum += arr[i];  }  //少于3个就优惠不了if (n < 3) {  System.out.println(sum);  return;  }  Arrays.sort(arr);  Queue<Long> deque = new LinkedList<>();  //模拟队列中第二个元素long max = arr[n - 2];//标志位  boolean isUsed = false;  for(int i = n - 3; cnt > 0 && i >= 0; i--) {  if (isUsed) {//模拟弹出后需要把队列顶部两个元素模拟弹出  if (deque.size() < 2) {  deque.add(arr[i]);  } else {  deque.poll();  max = deque.poll();  isUsed = false;  }  }  if(!isUsed) {  if (arr[i] * 2 <= max) {  isUsed = true;//模拟弹出//***, 退钱   sum -= arr[i];  cnt--;  } else {  deque.add(arr[i]);  }  }  }  System.out.println(sum);  }  
}