day-14 使数组和小于等于 x 的最少时间

思路
操作次数0-nums1.size()之间
时间复杂度: O(n²)
空间复杂度: O(n)
Code:
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];int[][] nums = new int[n][0];for (int i = 0; i < n; ++i) {nums[i] = new int[] {nums1.get(i), nums2.get(i)};}Arrays.sort(nums, Comparator.comparingInt(a -> a[1]));for (int i = 1; i <= n; ++i) {for (int j = 0; j <= n; ++j) {f[i][j] = f[i - 1][j];if (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);}}}int s1 = 0, s2 = 0;for (int v : nums1) {s1 += v;}for (int v : nums2) {s2 += v;}for (int j = 0; j <= n; ++j) {if (s1 + s2 * j - f[n][j] <= x) {return j;}}return -1;}
}
注:不会,参考了题解。。。。。。