【状态机dp】【排序】 2809使数组和小于等于 x 的最少时间

本文涉及知识点

【状态机dp】排序

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

给你两个长度相等下标从 0 开始的整数数组 nums1 和 nums2 。每一秒，对于所有下标 0 <= i < nums1.length ，nums1[i] 的值都增加 nums2[i] 。操作完成后，你可以进行如下操作：
选择任一满足 0 <= i < nums1.length 的下标 i ，并使 nums1[i] = 0 。
同时给你一个整数 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 。

提示：

1 <= nums1.length <= 10³
1 <= nums1[i] <= 10³
0 <= nums2[i] <= 10³
nums1.length == nums2.length
0 <= x <= 10⁶

状态机dp

sum1 = $\sum$ nums1 sum2 = $\sum$ nums2 n = nums1.length
sum1的最终值有两部分组成：
一，每秒增加sum2。
二，清零。减少当前nums1[i]。
性质一：对任意i清零两次，和只清第二次减少的值一样。
性质二：没必要对任意i清零两次，删除第一次清零i。最终值减少sum2。
性质三：由于不存在重复的i，故如果n秒搞不定，则永远搞不定。
性质四：如果某个最优解清零了S = {i1,i2,i3 $\dots$ }，那么按nums2[i]的升序清零，一定是最优解，i $\in$ S。

解法

indexs是nums2的下标，nums[indexs[i]] 升序排序。
dp[i][j] 表示处理完indexs的前i个数，操作了j秒清0的最大值

错误想法

看题解前，最终选取了m个，已经选择了j个。

代码

核心代码

 class Solution {public:int minimumTime(vector<int>& nums1, vector<int>& nums2, int x) {const int n = nums1.size();const int sum1 = std::accumulate(nums1.begin(), nums1.end(), 0);const int sum2 = std::accumulate(nums2.begin(), nums2.end(), 0);if (sum1 <= x) { return 0; }vector<int> indexs(n);iota(indexs.begin(), indexs.end(), 0);sort(indexs.begin(), indexs.end(), [&](const int& i1, const int& i2) {return nums2[i1] < nums2[i2]; });vector<vector<int>> dp(n+1, vector<int>(n + 1,INT_MIN));//dp[i][j] 表示处理完nums的前i个数，化了j秒清0的最大值dp[0][0] = 0;for (int i = 0; i < n; i++){const int index = indexs[i];for (int j = 0; j <= n; j++) {if (INT_MIN == dp[i][j]) { continue; }dp[i + 1][j] = max(dp[i + 1][j], dp[i ][j]);//第i+1个元素不选择if (j < n) {//第i+1个元素选择dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + nums1[index]+nums2[index]*(j+1));}} }for (int i = 1; i <= n; i++){int iMax = 0;for (int j = 0; j <= n; j++){iMax = max(iMax, dp[j][i]);}if (sum1 + sum2 * i - iMax <= x){return i;}}return -1;}};

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{assert(t1 == t2);
}template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{if (v1.size() != v2.size()){assert(false);return;}for (int i = 0; i < v1.size(); i++){Assert(v1[i], v2[i]);}}int main()
{vector<int> nums1, nums2;int x;{Solution sln;nums1 = { 1, 2, 3 }, nums2 = { 1, 2, 3 }, x = 4;auto res = sln.minimumTime(nums1, nums2, x);Assert(res, 3);}}

封装了类

template<class TSave,class TRecord>
class CSingUpdateLineTree
{
public:CSingUpdateLineTree(int iEleSize):m_iEleSize(iEleSize), m_vSave(iEleSize*4){}void Update(int index, TRecord update) {Update(1, 1, m_iEleSize, index + 1, update);}void Query(int leftIndex, int leftRight) {Query(1, 1, m_iEleSize, leftIndex + 1, leftRight + 1);}void Init() {Init(1, 1, m_iEleSize);}const int m_iEleSize;
protected:void Init(int iNodeNO, int iSaveLeft, int iSaveRight){if (iSaveLeft == iSaveRight) {OnInit(m_vSave[iNodeNO], iSaveLeft);return;}const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;Init(iNodeNO * 2, iSaveLeft, mid);Init(iNodeNO * 2+1, mid+1, iSaveRight);OnUpdateParent(m_vSave[iNodeNO], m_vSave[iNodeNO * 2], m_vSave[iNodeNO * 2 + 1], iSaveLeft, iSaveRight);}void Query(int iNodeNO, int iSaveLeft, int iSaveRight, int iQueryLeft,int iQueryRight) {if (( iSaveLeft >= iQueryLeft) && (iSaveRight <= iQueryRight )) {OnQuery(m_vSave[iNodeNO]);return;}if (iSaveLeft == iSaveRight) {//没有子节点return;}const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;if (mid >= iQueryLeft) {Query(iNodeNO * 2, iSaveLeft, mid, iQueryLeft, iQueryRight);}if( mid+1 <= iQueryRight ){Query(iNodeNO * 2+1, mid+1, iSaveRight, iQueryLeft, iQueryRight);}}void Update(int iNodeNO,int iSaveLeft,int iSaveRight,int iUpdateNO, TRecord update) {if (iSaveLeft == iSaveRight){OnUpdate(m_vSave[iNodeNO], update);return;}const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;if (iUpdateNO <= mid) {Update(iNodeNO * 2, iSaveLeft, mid, iUpdateNO, update);}else {Update(iNodeNO * 2+1, mid+1, iSaveRight, iUpdateNO, update);}OnUpdateParent(m_vSave[iNodeNO], m_vSave[iNodeNO * 2], m_vSave[iNodeNO * 2+1],iSaveLeft,iSaveRight);}virtual void OnInit(TSave& save,int iSave)=0;virtual void OnQuery(TSave& save) = 0;virtual void OnUpdate(TSave& save, const TRecord& update) = 0;virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r,int iSaveLeft,int iSaveRight) = 0;vector<TSave> m_vSave;
};template<class TSave = std::pair<int,int>, class TRecord = int >
class CMyLineTree : public CSingUpdateLineTree<TSave, TRecord>
{
public:CMyLineTree(const vector<int>& arr):CSingUpdateLineTree<TSave,TRecord>(arr.size()){m_arr = arr;const int iMax = *std::max_element(arr.begin(), arr.end());m_vIndexs.resize(iMax + 1);for (int i = 0; i < arr.size(); i++){m_vIndexs[arr[i]].emplace_back(i);}CSingUpdateLineTree<TSave, TRecord>::Init();}int Query(int left, int r, int threshold){m_vCan.clear();CSingUpdateLineTree<TSave, TRecord>::Query(left,r);auto [i1, i2] = Query(left, r, m_vCan);return (i2 >= threshold) ? i1 : -1;}
protected:vector<int> m_vCan;virtual void OnQuery(TSave& save) override{m_vCan.emplace_back(save.first);}virtual void OnUpdate(TSave& save, const TRecord& update) override{save = { update,1 };}virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r, int iSaveLeft, int iSaveRight) override{vector<int> vCan = { left.first,r.first };par = Query(iSaveLeft - 1, iSaveRight - 1, vCan);}std::pair<int, int> Query(int left, int r, vector<int> vCan){for (const auto& n : vCan){if (-1 == n) {continue;}auto it1 = std::lower_bound(m_vIndexs[n].begin(), m_vIndexs[n].end(), left);auto it2 = std::upper_bound(m_vIndexs[n].begin(), m_vIndexs[n].end(), r);const int iCnt = it2 - it1;if (2 * iCnt > (r - left + 1)){return { n,iCnt };}}return { -1,0 };}vector<vector<int>> m_vIndexs;vector<int> m_arr;virtual void OnInit(TSave& save, int iSave) override{save = { m_arr[iSave - 1],1 };}
};class MajorityChecker {
public:MajorityChecker(vector<int>& arr) :m_lineTree(arr) {}int query(int left, int right, int threshold) {return m_lineTree.Query(left, right, threshold);}CMyLineTree<> m_lineTree;
};

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛