力扣刷题第五天 使数组和小于等于x的最小时间

题目：使数组和小于等于x的最小时间

实例：

解题思路：

        每一秒，对于所有下标 0 <= i < nums1.length ，nums1[i] 的值都增加 nums2[i]，观察重置为零的数，会按照 nums2的速度增长，所以对于所有操作的数，我们应该优先操作增长速度慢的数。这样就可以出去更多的数。最终结果应为nums1的和加上nums2的和再减去可以消掉的最大数目。

       让我们按照 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。

class Solution {
public:
    int minimumTime(vector<int>& nums1, vector<int>& nums2, int x) {
        int n = nums1.size();
        vector<vector<int>> dp(n+1,vector<int>(n+1,0));
        vector<pair<int,int>> nums(n);
        for(int i=0;i<n;i++)
        {
            nums[i] = {nums2[i],nums1[i]};
        }
        sort(nums.begin(),nums.end());

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

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