【LeetCode每日一题】2809. 使数组和小于等于 x 的最少时间

发布时间:2024年01月19日

2024-1-19

2809. 使数组和小于等于 x 的最少时间

在这里插入图片描述

思路:
  1. 获取两个列表的长度n,并初始化一个二维数组f,用于存储最优解。
  2. 定义一个二维数组nums,用于存储输入的两个列表中的元素,并按照第二列元素进行排序。
  3. 使用动态规划的方法,通过遍历nums数组,计算最优解。其中,f[i][j]表示将前i个元素分配到j个集合中时的最大总和。通过比较f[i-1][j]和f[i-1][j-1]+a+b*j的大小,更新f[i][j]。
  4. 计算两个列表中所有元素的和,分别存储在s1和s2中。
  5. 遍历0至n的范围,判断是否满足条件s1 + s2 * j - f[n][j] <= x,若满足则返回j。
  6. 若没有满足条件的j值,则返回-1
class Solution {
    public int minimumTime(List<Integer> nums1, List<Integer> nums2, int x) {
        int n = nums1.size();
        int[][] f = new int[n + 1][n + 1]; // 定义二维数组f,用于存储最优解
        int[][] nums = new int[n][0]; // 定义二维数组nums,用于存储输入的两个列表中的元素
        for (int i = 0; i < n; ++i) {
            nums[i] = new int[] {nums1.get(i), nums2.get(i)}; // 将输入的两个列表中的元素按照相同的索引放入nums数组中
        }
        Arrays.sort(nums, Comparator.comparingInt(a -> a[1])); // 根据nums数组中第二列的元素进行排序
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= n; ++j) {
                f[i][j] = f[i - 1][j]; // 初始化f[i][j]为f[i-1][j]
                if (j > 0) { // 当j大于0时,进行以下操作
                    int a = nums[i - 1][0], b = nums[i - 1][1];
                    f[i][j] = Math.max(f[i][j], f[i - 1][j - 1] + a + b * j); // 更新f[i][j],取当前值与f[i-1][j-1]+a+b*j的较大值
                }
            }
        }
        int s1 = 0, s2 = 0;
        for (int v : nums1) {
            s1 += v; // 计算nums1列表中所有元素的和,存储在s1中
        }
        for (int v : nums2) {
            s2 += v; // 计算nums2列表中所有元素的和,存储在s2中
        }

        for (int j = 0; j <= n; ++j) {
            if (s1 + s2 * j - f[n][j] <= x) { // 判断是否满足条件 s1 + s2 * j - f[n][j] <= x
                return j; // 返回满足条件的j值
            }
        }
        return -1; // 若没有满足条件的j值,则返回-1
    }
}

点击移步博客主页,欢迎光临~

偷cyk的图

文章来源:https://blog.csdn.net/m0_64003319/article/details/135696638
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。