阿里云开发者社区在线编程56.Tom爱吃巧克力

Tom爱吃巧克力5aO无知

概述：5aO无知

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块巧克力花的最少钱数5aO无知

5aO无知

示例1

输入：
2
5
[[4,5],[2,4]]
输出：
12

解题思路

这是一个成本计算题，要买足够的货，一家店又买不足，就得去多家店买，而每家店的价格又不一样，这就是从价格最低的开始买，直到数量买够为止。难点在于对二维数组进行排序，也就是1维按升序2维按降序排列；排序完成之后，逐个开始计算，直到数量够了为止。5aO无知

正确解答

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;
    }
}

如果你是采购，需要大批采购物资，这个一定要会。5aO无知

5aO无知

本文由 微wx笑 创作，采用 署名-非商业性使用-相同方式共享 4.0 许可协议，转载请附上原文出处链接及本声明。
原文链接：https://www.ivu4e.cn/blog/algorithm/2020-07-16/510.html

很赞哦！ () 赏 有话说 ()