算法您现在的位置是:首页 > 博客日志 > 算法

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

<a href='mailto:'>微wx笑</a>的头像微wx笑2020-07-16 20:18:24算法人已围观关键字:   

Tom爱吃巧克力概述:Tom非常喜欢巧克力,他上次买的巧克力吃完了,所以他打算再去买k块巧克力回来(1<=k<=1e5),他又是一个非常节俭的一个人,所以他想花最少的钱去买巧克力,现在有n家

Tom爱吃巧克力n4f编程技术_踩坑日志_进阶指南_无知人生

概述:n4f编程技术_踩坑日志_进阶指南_无知人生

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块巧克力花的最少钱数n4f编程技术_踩坑日志_进阶指南_无知人生


n4f编程技术_踩坑日志_进阶指南_无知人生

示例1

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

解题思路

这是一个成本计算题,要买足够的货,一家店又买不足,就得去多家店买,而每家店的价格又不一样,这就是从价格最低的开始买,直到数量买够为止。难点在于对二维数组进行排序,也就是1维按升序2维按降序排列;排序完成之后,逐个开始计算,直到数量够了为止。n4f编程技术_踩坑日志_进阶指南_无知人生

正确解答

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

如果你是采购,需要大批采购物资,这个一定要会。n4f编程技术_踩坑日志_进阶指南_无知人生


n4f编程技术_踩坑日志_进阶指南_无知人生

本文由 微wx笑 创作,采用 CC BY-NC 4.0 许可协议。 非商业性使用可自由转载、引用、甚至修改,但需署名作者且注明出处。

很赞哦! () 有话说 ()

相关文章