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

2024-1-19

文章目录

- - - [2809. 使数组和小于等于 x 的最少时间](https://leetcode.cn/problems/minimum-time-to-make-array-sum-at-most-x/)
    - - 思路：

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

思路：

获取两个列表的长度n，并初始化一个二维数组f，用于存储最优解。
定义一个二维数组nums，用于存储输入的两个列表中的元素，并按照第二列元素进行排序。
使用动态规划的方法，通过遍历nums数组，计算最优解。其中，f[i][j]表示将前i个元素分配到j个集合中时的最大总和。通过比较f[i-1][j]和f[i-1][j-1]+a+b*j的大小，更新f[i][j]。
计算两个列表中所有元素的和，分别存储在s1和s2中。
遍历0至n的范围，判断是否满足条件s1 + s2 * j - f[n][j] <= x，若满足则返回j。
若没有满足条件的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
    }
}