AcWing 每日一题 2022/5/3【2040. 礼物】

农夫约翰想给他的 N 头奶牛购买礼物,但是他的预算只有 B 元。 奶牛 i 希望获得的礼物的价格…

农夫约翰想给他的 N 头奶牛购买礼物,但是他的预算只有 B 元。

奶牛 i 希望获得的礼物的价格为 Pi,运输成本为 Si,也就是说约翰要帮奶牛 i 买礼物,共需花费 Pi+Si 元钱。

约翰有一张特殊的优惠券,如果使用该优惠券来订购一份礼物,那么该礼物的价格会变为只有正常价格的一半。

如果约翰用该优惠券给奶牛 i 买礼物,那么他只需要支付 Pi/2+Si 元钱。

方便起见,Pi 一定是偶数。

请帮助约翰确定他最多可以给多少头奶牛购买礼物。

输入格式
第一行包含两个整数 N 和 B。

接下来 N 行,每行包含两个整数 Pi 和 Si。

输出格式
输出约翰可以购买礼物的奶牛最大数量。

数据范围

1≤N≤1000,
1≤B≤109,
0≤Pi,Si≤109

输入样例:

输出样例:

样例解释
一种最佳方案是约翰给前 4 头奶牛购买礼物,在给第 3 头奶牛购买礼物时使用优惠券。

花费为 (4+2)+(2+0)+(4+1)+(6+3)=22。

题目分析

对于每一件物品有一个价格和一个运输价格,我们有且只有一张优惠券,而优惠券仅可对原价格进行半价优惠,我们要就算在预算范围内,最多可以购买多少个礼物
误区:直接进行排序,优先选择最低价格的礼物,同时判断对超出预算的第一个礼物进行优惠处理是否可以继续购买
样例
2 170
10 100
20 50
正解:由于数据范围只有 1000 直接进行暴力枚举即可,枚举对每一个礼物进行优惠,所能购买的最大数量
时间复杂度:O(106)

本文来自网络,不代表软粉网立场,转载请注明出处:https://www.rfff.net/p/3786.html

作者: HUI

发表评论

您的电子邮箱地址不会被公开。

返回顶部