列表

详情

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

给你两个长度相等下标从 0 开始的整数数组 nums1 和 nums2 。每一秒，对于所有下标 0 <= i < nums1.length ，nums1[i] 的值都增加 nums2[i] 。操作 完成后 ，你可以进行如下操作：

同时给你一个整数 x 。

请你返回使 nums1 中所有元素之和 小于等于 x 所需要的 最少 时间，如果无法实现，那么返回 -1 。

 

示例 1：

输入：nums1 = [1,2,3], nums2 = [1,2,3], x = 4
输出：3
解释：
第 1 秒，我们对 i = 0 进行操作，得到 nums1 = [0,2+2,3+3] = [0,4,6] 。
第 2 秒，我们对 i = 1 进行操作，得到 nums1 = [0+1,0,6+3] = [1,0,9] 。
第 3 秒，我们对 i = 2 进行操作，得到 nums1 = [1+1,0+2,0] = [2,2,0] 。
现在 nums1 的和为 4 。不存在更少次数的操作，所以我们返回 3 。

示例 2：

输入：nums1 = [1,2,3], nums2 = [3,3,3], x = 4
输出：-1
解释：不管如何操作，nums1 的和总是会超过 x 。

 

提示：

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: int minimumTime(vector<int>& nums1, vector<int>& nums2, int x) { } };

rust 解法, 执行用时: 6 ms, 内存消耗: 2.1 MB, 提交时间: 2024-01-19 07:50:31 

impl Solution {
    pub fn minimum_time(nums1: Vec<i32>, nums2: Vec<i32>, x: i32) -> i32 {
        let mut pairs = nums1.iter().zip(nums2.iter()).collect::<Vec<_>>();
        pairs.sort_unstable_by(|&a, &b| a.1.cmp(&b.1));

        let n = pairs.len();
        let mut f = vec![0; n + 1];
        for (i, &(a, b)) in pairs.iter().enumerate() {
            for j in (1..=i + 1).rev() {
                f[j] = f[j].max(f[j - 1] + a + b * j as i32);
            }
        }

        let s1 = nums1.iter().sum::<i32>();
        let s2 = nums2.iter().sum::<i32>();
        for (t, &v) in f.iter().enumerate() {
            if s1 + s2 * t as i32 - v <= x {
                return t as i32;
            }
        }
        -1
    }
}

javascript 解法, 执行用时: 127 ms, 内存消耗: 57 MB, 提交时间: 2024-01-19 07:50:16 

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @param {number} x
 * @return {number}
 */
var minimumTime = function(nums1, nums2, x) {
    const pairs = _.zip(nums1, nums2).sort((a, b) => a[1] - b[1]);
    const n = pairs.length;
    const f = Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        const [a, b] = pairs[i];
        for (let j = i + 1; j; j--) {
            f[j] = Math.max(f[j], f[j - 1] + a + b * j);
        }
    }

    const s1 = _.sum(nums1);
    const s2 = _.sum(nums2);
    for (let t = 0; t <= n; t++) {
        if (s1 + s2 * t - f[t] <= x) {
            return t;
        }
    }
    return -1;
};

golang 解法, 执行用时: 40 ms, 内存消耗: 6.5 MB, 提交时间: 2023-08-07 16:00:58 

func minimumTime(nums1, nums2 []int, x int) int {
	s1, s2, n := 0, 0, len(nums1)
	id := make([]int, n)
	for i := range id {
		id[i] = i
		s1 += nums1[i]
		s2 += nums2[i]
	}
	sort.Slice(id, func(i, j int) bool { return nums2[id[i]] < nums2[id[j]] })

	f := make([]int, n+1)
	for _, i := range id {
		for j := n; j > 0; j-- {
			f[j] = max(f[j], f[j-1]+nums1[i]+nums2[i]*j)
		}
	}

	for t, v := range f {
		if s1+s2*t-v <= x {
			return t
		}
	}
	return -1
}

func max(a, b int) int { if b > a { return b }; return a }

cpp 解法, 执行用时: 212 ms, 内存消耗: 60.9 MB, 提交时间: 2023-08-07 16:00:43 

class Solution {
public:
    int minimumTime(vector<int> &nums1, vector<int> &nums2, int x) {
        int n = nums1.size();
        // 对下标数组排序，避免破坏 nums1 和 nums2 的对应关系
        vector<int> ids(n);
        iota(ids.begin(), ids.end(), 0);
        sort(ids.begin(), ids.end(), [&](const int i, const int j) {
            return nums2[i] < nums2[j];
        });

        vector<int> f(n + 1);
        for (int i: ids)
            for (int j = n; j; j--)
                f[j] = max(f[j], f[j - 1] + nums1[i] + nums2[i] * j);

        int s1 = accumulate(nums1.begin(), nums1.end(), 0);
        int s2 = accumulate(nums2.begin(), nums2.end(), 0);
        for (int t = 0; t <= n; t++)
            if (s1 + s2 * t - f[t] <= x)
                return t;
        return -1;
    }
};

java 解法, 执行用时: 103 ms, 内存消耗: 42.7 MB, 提交时间: 2023-08-07 16:00:23 

class Solution {
    public int minimumTime(List<Integer> nums1, List<Integer> nums2, int x) {
        int n = nums1.size(), s1 = 0, s2 = 0;
        // 对下标数组排序，避免破坏 nums1 和 nums2 的对应关系
        var ids = new Integer[n];
        for (int i = 0; i < n; i++) {
            ids[i] = i;
            s1 += nums1.get(i);
            s2 += nums2.get(i);
        }
        Arrays.sort(ids, (i, j) -> nums2.get(i) - nums2.get(j));

        var f = new int[n + 1];
        for (int i : ids)
            for (int j = n; j > 0; j--)
                f[j] = Math.max(f[j], f[j - 1] + nums1.get(i) + nums2.get(i) * j);

        for (int t = 0; t <= n; t++)
            if (s1 + s2 * t - f[t] <= x)
                return t;
        return -1;
    }
}

python3 解法, 执行用时: 2024 ms, 内存消耗: 16.3 MB, 提交时间: 2023-08-07 15:59:39 

'''
动态规划
定义 f[i+1][j] 表示从前 i 个数中选出 j 个数，减少量最大是多少。
考虑第 i 个数「选或不选」：
不选：f[i+1][j]=f[i][j]。
选：f[i+1][j]=f[i][j−1]+nums1[i] + nums2[i] * j

第一维优化，0-1背包倒序循环j
'''

class Solution:
    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:
        n = len(nums1)
        f = [0] * (n + 1)
        for a, b in sorted(zip(nums1, nums2), key=lambda z: z[1]):
            for j in range(n, 0, -1):
                f[j] = max(f[j], f[j - 1] + a + b * j)

        s1 = sum(nums1)
        s2 = sum(nums2)
        for t, v in enumerate(f):
            if s1 + s2 * t - v <= x:
                return t
        return -1

上一题

© 2024 leetcode.cn