2809. 使数组和小于等于 x 的最少时间 - 力扣（LeetCode）https://leetcode.cn/problems/minimum-time-to-make-array-sum-at-most-x/?envType=daily-question&envId=2024-01-19

 经典动态规划

class Solution {
public:int minimumTime(vector<int>& nums1, vector<int>& nums2, int x) {int n = nums1.size();vector<int> ind(n);iota(ind.begin(), ind.end(), 0);sort(ind.begin(), ind.end(), [&](int i, int j) {return nums2[i] < nums2[j];});vector<int> f(n + 1);//f[i]:前n个数操作i次最大减少量for (int i = 0; i < n; i++) {for (int j = i + 1; j > 0; j--) {f[j] = max(f[j], f[j - 1] + nums1[ind[i]] + nums2[ind[i]] * j);}}   int s1 = accumulate(nums1.begin(), nums1.end(), 0);int s2 = accumulate(nums2.begin(), nums2.end(), 0);for (int i = 0; i <= n; i++) {if (s1 + i * s2 - f[i] <= x) {return i;}}return -1;}
};