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

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

选择任一满足 0 <= i < nums1.length 的下标 i ，并使 nums1[i] = 0 。

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

每个数最多归0一次，大的nums2晚归0。将nums2从小到大排序，从中找一个nums[j]，经历length-j秒，对i<j，num[i]=nums1[i]+(length-j)*nums2[i]，对i≥j，num[i]=(length-i)*nums2[i]，num[i]小于等于x。如果找不到j，则返回-1；否则返回(length-j_max)

首先，我们可以发现，每一次操作使得 nums1[i]=0，对于每一个 nums1[i]最多需要进行一次这样的操作。如果设置两次，可以简单地移除前一次设置。

观察重置为零的数，会按照 nums2 的速度增长，所以对于所有操作的数，我们应该优先操作增长速度慢的数。
如果我们选择多个索引 i₁,i₂,…,i_k
，那么按照 nums2[i1]≤nums2[i2]≤…≤nums2[ik] 的顺序进行设置是最优的。

让我们按照 nums2的大小对所有数值对进行排序（非递减顺序）。用 dp[j][i]表示如果对前 j 个元素进行 i 次操作，可以减少的最大总值，初始值为零。对于第 j 个元素，我们可以选择对其进行操作或者不操作，由此可以得到状态转移方程：

dp[j][i]=max?(dp[j?1][i],dp[j?1][i?1]+nums2[j?1]×i+nums1[j?1])
其中有 1≤i≤j≤n。

最后我们返回最小的 t，使满足 sum(nums1)+sum(nums2)×t?dp[n][t]≤x，如果不存在返回-1。

C

static int cmp(const void *a, const void *b) {
    return ((int *)a)[0] - ((int *)b)[0];
}

int minimumTime(int* nums1, int nums1Size, int* nums2, int nums2Size, int x) {
    int n = nums1Size;
    int dp[n + 1][n + 1];
    int nums[n][2];
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < n; i++) {
        nums[i][0] = nums2[i];
        nums[i][1] = nums1[i];
    }
    qsort(nums, n, sizeof(nums[0]), cmp);

    for (int j = 1; j <= n; j++) {
        int b = nums[j - 1][0], a = nums[j - 1][1];
        for (int i = j; i > 0; i--) {
            dp[j][i] = fmax(dp[j - 1][i], dp[j - 1][i - 1] + i * b + a);
        }
    }

    int s1 = 0, s2 = 0;
    for (int i = 0; i < n; i++) {
        s1 += nums1[i];
        s2 += nums2[i];
    }
    for (int i = 0; i <= n; i++) {
        if (s2 * i + s1 - dp[n][i] <= x) {
            return i;
        }
    }
    return -1;
}

python

class Solution:
    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:
        n = len(nums1)
        dp = [[0] * (n + 1) for _ in range(n + 1)]
        for j, (b, a) in enumerate(sorted(zip(nums2, nums1)), 1):
            for i in range(j, 0, -1):
                dp[j][i] = max(dp[j - 1][i], dp[j - 1][i - 1] + i * b + a)
        sa, sb = sum(nums1), sum(nums2)
        for i in range(0, n + 1):
            if sb * i + sa - dp[n][i] <= x:
                return i
        return -1