Problem 3417 --采购大米

3417: 采购大米

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $40$ 正确数量 $9$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 贪心

目前全国都在饱受新型冠状病毒疫情的困扰,疫情当前我们最大的贡献就是闭门不出。同时各个社区也有社区志愿者战斗在”防疫一线”,帮助居民采购生活物资,在社区门口管理和登记车辆和行人的出口等。小创的妈妈就是社区志愿者中的一员,负责物资的采购,而今天要采购的物资是大米,小创的妈妈一共需要采买M斤大米,小创的妈妈已经拿到了N名大米供应商的信息,每个供应商的价格不同,每个供应商的供应量也不一定相同,小创的妈妈需要挑选出一些供应商来满足采买需求。

但是小创的妈妈比较头疼,若要采购足够量的大米(如果总的供应量不足,那么尽可能的购买最多),如何采购才能使得花费最小呢?请你帮助小创的妈妈来解决这个问题吧。

第一行,两个整数N和M,N表示的是大米供应商的数量,M表示需要采买的大米总量。

1≤N≤1000,0≤M≤10^6

接下来N行,是用空格隔开的一个小数和一个整数,分别表示第i个供应商的单价xi和这个供应商的供应量yi

1≤Xi≤10,0≤yi≤10^6

一行,一个小数,表示小创妈妈要采购M斤大米所需要的最小花费,小数点后保留一位小数。
5 1000
1.9 100
2.1 200
1.8 300
2.2 800
2.5 400
2030.0
需要采购的代码是1000斤,1.8元的供应商采购300斤,1.9元的供应商采购100斤,2.1元的供应商采购200斤,2.2元的供应商采购400斤,总花费是2030.0元

推荐代码 查看3417 所有题解 上传题解视频得图灵币

本题记录 用 户(点击查看用户) 运行号(点击购买题解) 时 间
算法最快[$0 $ms] 只能过个样例~~~ 758679 2021-07-05 22:40:49
内存最少[$2088 $KB] .irony 760347 2021-07-08 11:25:08
第一AC AOJ大管家 613123 2020-09-26 15:16:37
第一挑战 AOJ大管家 613123 2020-09-26 15:16:37

赛题来源/所属竞赛 贪心算法 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛
1656 2021-2022-1学期<算法分析与设计> 期初补考试练习赛 2021-09-05 00:00:00 请登录
1619 2020-2021-2学期<算法分析与设计ZJ28104> 期末考试【19计算机12】正式考试 2021-07-08 10:00:00 请登录