网站制作源码版权,优化公司排行榜,软件公司简介内容怎么写,宁夏做网站的题目描述
【问题描述】 某商场有 N 件商品#xff0c;其中第 i 件的价格是 A i 。现在该商场正在进行 “ 买二 赠一” 的优惠活动#xff0c;具体规则是#xff1a; 每购买 2 件商品#xff0c;假设其中较便宜的价格是 P #xff08;如果两件商品价格一样#xff0c; 则…题目描述
【问题描述】 某商场有 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); QueueLong 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); }
}具体代码参上
好的!本次分享到这就结束了 如果对铁汁你有帮助的话记得点赞收藏⭐️关注➕ 我在这先行拜谢了
