【力扣-1710打卡】

淩亂°似流年 2023-09-26 16:41 45阅读 0赞

package com.example.demomain.demoleetcode.easy;
 
 import org.junit.Test;
 
 import java.util.Arrays;
 
 /**
 * 请你将一些箱子装在 一辆卡车 上。给你一个二维数组 boxTypes ，其中 boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi] ：
 * 
 * numberOfBoxesi 是类型 i 的箱子的数量。
 * numberOfUnitsPerBoxi 是类型 i 每个箱子可以装载的单元数量。
 * 整数 truckSize 表示卡车上可以装载 箱子 的 最大数量 。只要箱子数量不超过 truckSize ，你就可以选择任意箱子装到卡车上。
 * 
 * 返回卡车可以装载 单元 的 最大 总数。
 * 
 * 示例 1：
 * 
 * 输入：boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4
 * 输出：8
 * 解释：箱子的情况如下：
 * - 1 个第一类的箱子，里面含 3 个单元。
 * - 2 个第二类的箱子，每个里面含 2 个单元。
 * - 3 个第三类的箱子，每个里面含 1 个单元。
 * 可以选择第一类和第二类的所有箱子，以及第三类的一个箱子。
 * 单元总数 = (1 * 3) + (2 * 2) + (1 * 1) = 8
 * 示例 2：
 * 
 * 输入：boxTypes = [[5,10],[2,5],[4,7],[3,9]], truckSize = 10
 * 输出：91
 * 提示：
 * 
 * 1 <= boxTypes.length <= 1000
 * 1 <= numberOfBoxesi, numberOfUnitsPerBoxi <= 1000
 * 1 <= truckSize <= 106
 *
 * @author: lfsun
 * @time: 17:52
 * @date: 2022/11/15
 */
 public class MaximumUnits {
 
 
 /**
 * 贪心
 *
 * @param boxTypes
 * @param truckSize
 * @return
 */
 public int maximumUnits(int[][] boxTypes, int truckSize) {
 
 int n = boxTypes.length, result = 0;
 // 倒序排序，优先最大单元
 Arrays.sort(boxTypes, (a, b) -> b[1] - a[1]);
 for (int i = 0, count = 0; i < n && count < truckSize; i++) {
 
 int a = boxTypes[i][0], b = boxTypes[i][1], c = Math.min(a, truckSize - count);
 count += c;
 result += c * b;
 }
 return result;
 }
 
 /**
 * 计数排序
 * @param boxTypes
 * @param truckSize
 * @return
 */
 public int maximumUnitsByRow(int[][] boxTypes, int truckSize) {
 
 int count = 0;
 int[] ans = new int[1001];
 for (int[] is : boxTypes) {
 
 ans[is[1]] += is[0];
 }
 // 倒序遍历
 for (int i = ans.length - 1; i > 0; i--) {
 
 if (ans[i] != 0) {
 
 if (truckSize > ans[i]) {
 
 // 还可以装
 count += ans[i] * i;
 truckSize -= ans[i];
 } else {
 
 // 装不下了
 return count + truckSize * i;
 }
 }
 // 跳过 默认的0
 }
 return count;
 }
 
 @Test
 public void test() {
 
 int[][] boxTypes = {
 {
 5, 10}, {
 2, 5}, {
 4, 7}, {
 3, 9}};
 int truckSize = 10;
 //int result = maximumUnits(boxTypes, truckSize);
 //System.out.println(result);
 
 int result1 = maximumUnitsByRow(boxTypes, truckSize);
 System.out.println(result1);
 
 
 }
 }