阿里云开发者社区在线编程56.Tom爱吃巧克力
微wx笑
2020-07-16【算法】
269
5
0关键字:
Tom爱吃巧克力概述:Tom非常喜欢巧克力,他上次买的巧克力吃完了,所以他打算再去买k块巧克力回来(1<=k<=1e5),他又是一个非常节俭的一个人,所以他想花最少的钱去买巧克力,现在有n家
目录
Tom爱吃巧克力
概述:
Tom非常喜欢巧克力,他上次买的巧克力吃完了,所以他打算再去买k块巧克力回来(1<=k<=1e5),他又是一个非常节俭的一个人,所以他想花最少的钱去买巧克力,现在有n家卖巧克力的店(1<=n<=1e5),每个店的巧克力都限购bi块(最多只能买bi块,1<=bi<=1e5),每块的价格是ai(1<=ai<=1e9),请问Tom买k块巧克力最少要花多少钱。题目保证n个bi的总和大于等于k。
输入卖巧克力的店的个数n(1<=n<=1e5);打算去买的巧克力块数k(1<=k<=1e5);和一个数组m,其中mi =[ai, bi]
(1<=ai<=1e9,1<=bi<=1e5 )表示第i家巧克力店的巧克力的价格和限购块数
输出一个数,表示Tom买k块巧克力花的最少钱数
示例1
1 2 3 4 5 6 | 输入: 2 5 [[4,5],[2,4]] 输出: 12 |
解题思路
这是一个成本计算题,要买足够的货,一家店又买不足,就得去多家店买,而每家店的价格又不一样,这就是从价格最低的开始买,直到数量买够为止。难点在于对二维数组进行排序,也就是1维按升序2维按降序排列;排序完成之后,逐个开始计算,直到数量够了为止。
正确解答
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | package solution56; import java.util.*; class Solution { private static void sortByColumn( int [][] ob, final int [] order) { Arrays.sort(ob, new Comparator<Object>() { public int compare(Object o1, Object o2) { int [] one = ( int []) o1; int [] two = ( int []) o2; for ( int i = 0 ; i < order.length; i++) { int k = order[i]; if (one[k] > two[k]) { return 1 ; } else if (one[k] < two[k]) { return - 1 ; } else { continue ; } } return 0 ; } }); } public long solution( long n, long k, int [][] nums) { long money = 0 ; sortByColumn(nums, new int []{ 0 , 1 }); for ( int i = 0 ; i < nums.length; i++){ if (nums[i][ 1 ] < k){ money += nums[i][ 0 ] * nums[i][ 1 ]; k -= nums[i][ 1 ]; } else { money += nums[i][ 0 ] * k; break ; } } return money; } } |
如果你是采购,需要大批采购物资,这个一定要会。
本文由 微wx笑 创作,采用 署名-非商业性使用-相同方式共享 4.0 许可协议,转载请附上原文出处链接及本声明。
原文链接:https://www.ivu4e.cn/blog/algorithm/2020-07-16/510.html