题目描述
【问题描述】
某商场有 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
【样例输出】
25
【样例说明】
小明可以先购买价格 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);
}
}
具体代码参上
好的!本次分享到这就结束了
如果对铁汁你有帮助的话，记得点赞👍+收藏⭐️+关注➕
我在这先行拜谢了：）
