牛客小白月赛82 --- D题 Kevin逛超市 2 (困难版本)--- 题解

2023-12-02 15:12

本文主要是介绍牛客小白月赛82 --- D题 Kevin逛超市 2 (困难版本)--- 题解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

D题 Kevin逛超市

题目描述

输入描述:

输出描述:

输入

输出

说明

思路:

代码:


 

D题 Kevin逛超市

题目描述

Take that money, and watch it burn\sf Take\ that\ money,\ and\ watch\ it\ burnTake that money, and watch it burn

Sink in the river, the lessons I’ve learned\sf Sink\ in\ the\ river,\ the\ lessons\ I’ve\ learnedSink in the river, the lessons I’ve learned

       —— Counting Stars, OneRepublicCounting\ Stars,\ \text{OneRepublic}Counting Stars, OneRepublic

两个版本唯一的不同是:简单版本中折扣券和立减券的数量均为 111,困难版本中折扣券和立减券的数量为给定值。


氧气少年在逛超市。

他总共买了 nnn 件商品,第 iii 种商品的价格为 pip_ipi​。

超市有下面的打折政策:

  •  每名顾客有 aaa 张折扣券,可以让一件商品的价格打折(如果此商品原价为 pip_ipi​,那么使用此优惠券后,价格变为 pi×x%p_i\times x\%pi​×x%)。
  •  每名顾客有 bbb 张立减券,可以让一件商品的价格减小 yyy(如果此商品原价小于 yyy,那么可以花费 000 买下)。
  •  每个商品最多使用 111 张优惠券。

请求出氧气少年可能付出的最小的花费。

输入描述:

第一行包含一个整数 T(1≤T≤10^5),表示测试用例的组数。对于每组测试用例:第一行包含五个整数 (1≤n≤2⋅10^5),(0≤a,b≤n),(1≤x≤99),(1≤y≤10^4)
第二行包含 n 个整数 p1…pn ,表示商品的价格。保证对于所有的测试用例,nnn 的总和不超过 2⋅10^5

输出描述:

对于每组测试用例:仅输出一行,包含一个实数,表示答案。如果你的答案和标准答案的绝对误差或相对误差不超过 10−410^{-4}10−4,则你的答案会被视为正确。

示例1

输入

6
3 2 1 50 50
100 100 50
3 3 1 50 200
100 100 45
3 2 2 36 3
5 8 1
3 3 3 99 500
100 600 1000
3 3 3 1 1
100 600 1000
3 0 0 1 1
100 600 1000

输出

100.000000000000
72.500000000000
4.680000000000
600.000000000000
17.000000000000
1700.000000000000

说明

对于第一组样例数据:
可以对编号为 1,21,21,2 的商品使用折扣券,对编号为 333 的商品使用立减券。对于第二组样例数据:
可以对编号为 1,31,31,3 的商品使用折扣券,对编号为 222 的商品使用立减券。

思路:

这道题就是一个简单的贪心,因为对于商品使用优惠券只有两种情况,要么使用折扣卷,要么使用立减卷,并且对于折扣卷来说,如果他的价值越高,折扣越多,所以优先对于价值高的物品使用折扣卷,然后对于立减卷来说,如果这个物品价值都高于他,那么他的作用是等同的,如果这个物品价值低于他,越高的物品价值,省去的钱越多。

所以通过这里分析可知,我们应该对价格高的(a+b)个物品使用优惠券,枚举这a+b个商品,不管优惠券数量,每个商品选择最优的优惠券使用,如果某个优惠券数量用多了(不妨设是x类型用多了),则考虑把一部分使用x类型的商品改为使用y类型,怎么改呢,这里又是一个贪心,把所有使用x类型优惠券的商品按“使用y的优惠减去使用x的优惠”排序,相当于如果算出改变这些商品使用的优惠券类型,带来的增量是多少,然后优先选择增量小的就行,直到优惠券数量平衡。

代码:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Arrays;
import java.util.Scanner;/*** @ProjectName: study3* @FileName: Ex34* @author:HWJ* @Data: 2023/12/2 9:43*/
public class Main {public static void main(String[] args) throws IOException {StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));in.nextToken();int t = (int)in.nval;for (int o = 0; o < t; o++) {in.nextToken();int n = (int) in.nval;in.nextToken();int a = (int) in.nval;in.nextToken();int b = (int) in.nval;in.nextToken();double x = (int) in.nval /100.0;in.nextToken();int y = (int) in.nval;double[][] arr = new double[n][3];double total = 0;for (int i = 0; i < n; i++) {in.nextToken();arr[i][0] = (int) in.nval;arr[i][1] = arr[i][0] * (1 - x);arr[i][2] = Math.min(arr[i][0], y);total+=arr[i][0];}int cntA = 0;int cntB = 0;Arrays.sort(arr, ((o1, o2) -> {return (int) (o2[0] - o1[0]);}));double[] df = new double[Math.min(a + b, n)];int p = 0;for (int i = 0; i < Math.min(a + b, n); i++) {if (arr[i][1] > arr[i][2]){total -= arr[i][1];cntA++;}else {total -= arr[i][2];cntB++;}df[p++] = arr[i][1] - arr[i][2];}Arrays.sort(df);if (cntA <= a && cntB <= b){System.out.println(total);} else if (cntA > a) {int k = cntA - a;for (int i = 0; i < a + b; i++) {if (df[i] <= 0) continue;total += df[i];k--;if (k == 0) break;}System.out.println(total);}else {int k = cntB - b;for (int i = Math.min(a + b, n) - 1; i >= 0; i--) {if (df[i] > 0) continue;total -= df[i];k--;if (k == 0) break;}System.out.println(total);}}}
}

这篇关于牛客小白月赛82 --- D题 Kevin逛超市 2 (困难版本)--- 题解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/445806

相关文章

Linux卸载自带jdk并安装新jdk版本的图文教程

《Linux卸载自带jdk并安装新jdk版本的图文教程》在Linux系统中,有时需要卸载预装的OpenJDK并安装特定版本的JDK,例如JDK1.8,所以本文给大家详细介绍了Linux卸载自带jdk并... 目录Ⅰ、卸载自带jdkⅡ、安装新版jdkⅠ、卸载自带jdk1、输入命令查看旧jdkrpm -qa

Tomcat版本与Java版本的关系及说明

《Tomcat版本与Java版本的关系及说明》:本文主要介绍Tomcat版本与Java版本的关系及说明,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Tomcat版本与Java版本的关系Tomcat历史版本对应的Java版本Tomcat支持哪些版本的pythonJ

IDEA中Git版本回退的两种实现方案

《IDEA中Git版本回退的两种实现方案》作为开发者,代码版本回退是日常高频操作,IntelliJIDEA集成了强大的Git工具链,但面对reset和revert两种核心回退方案,许多开发者仍存在选择... 目录一、版本回退前置知识二、Reset方案:整体改写历史1、IDEA图形化操作(推荐)1.1、查看提

JDK多版本共存并自由切换的操作指南(本文为JDK8和JDK17)

《JDK多版本共存并自由切换的操作指南(本文为JDK8和JDK17)》本文介绍了如何在Windows系统上配置多版本JDK(以JDK8和JDK17为例),并通过图文结合的方式给大家讲解了详细步骤,具有... 目录第一步 下载安装JDK第二步 配置环境变量第三步 切换JDK版本并验证可能遇到的问题前提:公司常

nvm如何切换与管理node版本

《nvm如何切换与管理node版本》:本文主要介绍nvm如何切换与管理node版本问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录nvm切换与管理node版本nvm安装nvm常用命令总结nvm切换与管理node版本nvm适用于多项目同时开发,然后项目适配no

Mybatis从3.4.0版本到3.5.7版本的迭代方法实现

《Mybatis从3.4.0版本到3.5.7版本的迭代方法实现》本文主要介绍了Mybatis从3.4.0版本到3.5.7版本的迭代方法实现,包括主要的功能增强、不兼容的更改和修复的错误,具有一定的参考... 目录一、3.4.01、主要的功能增强2、selectCursor example3、不兼容的更改二、

pytorch+torchvision+python版本对应及环境安装

《pytorch+torchvision+python版本对应及环境安装》本文主要介绍了pytorch+torchvision+python版本对应及环境安装,安装过程中需要注意Numpy版本的降级,... 目录一、版本对应二、安装命令(pip)1. 版本2. 安装全过程3. 命令相关解释参考文章一、版本对

springboot3.4和mybatis plus的版本问题的解决

《springboot3.4和mybatisplus的版本问题的解决》本文主要介绍了springboot3.4和mybatisplus的版本问题的解决,主要由于SpringBoot3.4与MyBat... 报错1:spring-boot-starter/3.4.0/spring-boot-starter-

mac安装nvm(node.js)多版本管理实践步骤

《mac安装nvm(node.js)多版本管理实践步骤》:本文主要介绍mac安装nvm(node.js)多版本管理的相关资料,NVM是一个用于管理多个Node.js版本的命令行工具,它允许开发者在... 目录NVM功能简介MAC安装实践一、下载nvm二、安装nvm三、安装node.js总结NVM功能简介N

java中不同版本JSONObject区别小结

《java中不同版本JSONObject区别小结》本文主要介绍了java中不同版本JSONObject区别小结,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们... 目录1. FastjsON2. Jackson3. Gson4. org.json6. 总结在Jav