56.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

解题思路

审题

• long n ：n家店
• long k : 需要购买的巧克力数

• int[][] nums : 所有巧克力店铺信息

  • int[i] nums: 代表一个店铺

    • nums[i][0]表示巧克力价格
    • nums[i][1]表示能够买的巧克力块数

题目要求

• 买k块巧克力花最少的钱

步骤

1. 定义变量 long money, 用来存储最终花费金额, 初始值为0；

2. 使用排序算法对nums数组排序, 按每块巧克力金额从小到大排序

   • 建议使用n^2以下的排序算法, 否则可能超时

3. 循环遍历每个店铺nums[i]

   • 如果当前需要购买的巧克力块数k大于店铺允许购买的块数nums[i][1], 则全部购买

     • 更新需要够买的巧克力块数k
     • 金额money 加上 购买巧克力块数 巧克力金额*

   • 如果当前需要购买的巧克力块数k 小于店铺允许购买的块数nums[i][1], 则购买k块巧克力

     • 金额money 加上 需要购买巧克力块数 巧克力金额*
     • 跳出循环
4. 返回所需金额money

题目的坑

• 问题：
  题目给出的nums数组为int类型, 而当购买所有的巧克力时, 需要使用到**nums[i][0] nums[i][1] 时，这个数将会超过int类型的最大值, 导致数据溢出, 造成最终结果错误的结果。

• 解决方法:
  每次 **nums[i][0] nums[i][1] 时, 先将两个数转为long类型, 这样就可以保证数据不会溢出。