【状态机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 <= 103
1 <= nums1[i] <= 103
0 <= nums2[i] <= 103
nums1.length == nums2.length
0 <= x <= 106

状态机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

相关

下载

想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

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

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/530480.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

MySQL-多表查询:多表查询分类、SQL99语法实现多表查询、UNION的使用、7种SQL JOINS的实现、SQL99语法新特性、多表查询SQL练习

多表查询 1. 一个案例引发的多表连接1.1 案例说明1.2 笛卡尔积&#xff08;或交叉连接&#xff09;的理解1.3 案例分析与问题解决 2. 多表查询分类讲解分类1&#xff1a;等值连接 vs 非等值连接等值连接非等值连接 分类2&#xff1a;自连接 vs 非自连接分类3&#xff1a;内连接…

结构型模式--3.组合模式【草帽大船团】

1. 好大一棵树 路飞在德雷斯罗萨打败多弗朗明哥之后&#xff0c;一些被路飞解救的海贼团自愿加入路飞麾下&#xff0c;自此组成了草帽大船团&#xff0c;旗下有7为船长&#xff0c;分别是&#xff1a; 俊美海贼团75人 巴托俱乐部56人 八宝水军1000人 艾迪欧海贼团4人 咚塔塔海…

Leetcode223. 矩形面积

Every day a Leetcode 题目来源&#xff1a;223. 矩形面积 解法1&#xff1a;数学 两个矩形覆盖的总面积等于两个矩形的面积之和减去两个矩形的重叠部分的面积。由于两个矩形的左下顶点和右上顶点已知&#xff0c;因此两个矩形的面积可以直接计算。如果两个矩形重叠&#xf…

Datacom HCIP笔记-MPLS协议 之二

在Ingress节点执行该命令时&#xff0c;触发所有的32位路由建立LDPLSP。 在Egress节点执行该命令时&#xff0c;触发本地32位路由建立LDPLSP&#xff0c; egress就是主机路由始发路由器 ingress就是主机路由非始发路由器 默认情况下&#xff1a;华为路由器仅为非物理接口主机路…

MCM制品图软件使用技巧-常见问题

常见问题 匀色效果不好 观察整体颜色是否一致&#xff1a;整体严重不一致时&#xff0c;使用参考匹配进行匀色处理&#xff1b;部分图层存在亮度色差时&#xff0c;使用人工调色对图层进行单独微调&#xff0c;比如提高亮度、对比度等等。局部纹理是否存在丢失&#xff0c;丢…

202.PyQt5_QTableWidget_项处理_表格控件

我 的 个 人 主 页:👉👉 失心疯的个人主页 👈👈 入 门 教 程 推 荐 :👉👉 Python零基础入门教程合集 👈👈 虚 拟 环 境 搭 建 :👉👉 Python项目虚拟环境(超详细讲解) 👈👈 PyQt5 系 列 教 程:👉👉 Python GUI(PyQt5)文章合集 👈👈 Oracle数…

数码相框-显示JPG图片

LCD控制器会将LCD上的屏幕数据映射在相应的显存位置上。 通过libjpeg把jpg图片解压出来RGB原始数据。 libjpeg是使用c语言实现的读写jpeg文件的库。 使用libjpeg的应用程序是以"scanline"为单位进行图像处理的。 libjpeg解压图片的步骤&#xff1a; libjpeg的使…

JVM字节码与类的加载——类的加载过程详解

文章目录 1、概述2、加载(Loading)阶段2.1、加载完成的操作2.2、二进制流的获取方式2.3、类模型与Class实例的位置2.4、数组类的加载 3、链接(Linking)阶段3.1、链接阶段之验证(Verification)3.1.1、格式检查3.1.2、字节码的语义检查3.1.3、字节码验证3.1.4、符号引用验证 3.2、…

最新mysql8.3 保姆级 主从复制搭建教程

mysql 主从复制搭建 服务器配置表 机器ip操作系统主机192.168.31.25华为openEuler-22.03-LTS-SP3从机192.168.31.184华为openEuler-22.03-LTS-SP3从机192.168.31.228华为openEuler-22.03-LTS-SP3 1、在3台机器上安装独立的 mysql 1.1 创建myql文件夹用来存放mysql包 mkdir…

网络安全之权限维持那点事

权限维持 一旦黑客成功地入侵了目标系统&#xff0c;他们通常会尝试保持对系统的持久访问权&#xff0c;以便继续执行恶意活动&#xff0c;如窃取敏感数据、植入恶意软件、破坏系统功能等。 权限维持的过程可能包括以下几个方面&#xff1a; 后门植入&#xff1a;黑客可能会在…

探秘大模型:《提示工程:技巧、方法与行业应用》背后的故事

提示工程是一种新兴的利用人工智能的技术&#xff0c;它通过设计提示引导生成式 AI 模型产生预期的输出&#xff0c;来提升人与 AI 的互动质量&#xff0c;激发 AI 模型的潜力&#xff0c;提升AI的应用水平。 为了让每一个人都拥有驱动大模型的能力&#xff0c;以微软全球副总裁…

C++设计模式:原型模式(八)

1、定义与动机 定义&#xff1a;使用原型实例指定创建对象的种类&#xff0c;然后通过拷贝这些原型来创建新的对象。 动机&#xff1a; 在软件系统中&#xff0c;经常面临着“某些结构复杂的对象”的创建工作&#xff1b;由于需求的变化&#xff0c;这些对象经常面临着剧烈的变…

Window安装PostgresSQL

PostgreSQL 安装参考&#xff1a;Windows下安装PostgreSQL_window 安装postgresql-CSDN博客 安装好后打开pgAdmin4 配置Navicat连接PostgresSQL 找到安装目录文件 pg_hba.conf 修改配置增加&#xff1a; 修改前&#xff1a; # TYPE DATABASE USER ADDRES…

AI论文精读之CSPNet—— 一种加强CNN模型学习能力的主干网络

目录 一、论文摘要部分 二、提出背景 三、本文的方法 3.1 DenseNet 3.2 Cross Stage Partial DenseNet 3.3 引入 partial dense block及partial transition layer的目的 3.3.1 partial dense block 3.3.2 partial transition layer 3.4 将CSPNet应用到其他结构中 3.5 E…

100 Explosion Pack

该套装包括100种爆炸效果,包括火灾爆炸、冲击波、风暴、奇异点、特斯拉等效果。 纹理有一个透明的alpha通道,所以你可以在任何背景上使用它们! 所有效果都是高质量的,动画流畅(64帧,每帧512像素) 每个效果都使用独特的高质量精灵表。 100个不同的小精灵大小:4096x4096 …

IO流(2.其他流)

能够高效读写的缓冲流&#xff0c;能够转换编码的转换流&#xff0c;能够持久化存储对象的序列化流 一、缓冲流 缓冲流,也叫高效流&#xff0c;是对4个基本的FileXxx 流的增强&#xff0c;所以也是4个流&#xff0c;按照数据类型分类&#xff1a; 字节缓冲流&#xff1a;Buffe…

【中文医疗词嵌入模型】SMedBERT:结构化知识图谱 + 混合注意力机制 + 提及-邻居上下文建模

【中文医疗词嵌入模型】SMedBERT&#xff1a;结构化知识图谱 混合注意力机制 提及-邻居上下文建模 提出背景SMedBERT 具体到点的设计逻辑SMedBERT的背景SMedBERT的工作原理 SMedBERT 具体实现细节3.1 符号和模型3.2 Top-K Entity Sorting3.3 提及-邻居混合注意力3.4 提及-邻居…

Softing工业将亮相2024汉诺威工业博览会——工业物联网的数据集成和连接

您可在2024年4月22至26日前往汉诺威参观Softing展台&#xff0c;我们将在015号馆的F48展位进行展出&#xff0c;期待您的莅临&#xff01; | 通过灵活的数据集成解决方案无缝连接机器 在此次汉诺威工业博览会上&#xff0c;您将了解到Softing数据集成解决方案——用于机器连接…

【深度学习|基础算法】初识Transformer-encoder-decoder

关于transformer的学习 一、前言二、初识Transformer2.1 总览2.2 encoder2.3 decoder 三. 流程与细节1、输入2、self-attention 一、前言 我本身是从事图像算法行业的&#xff0c;在之前主要是做传统的图像算法&#xff0c;后来接触了基于CNN的神经网络图像算法&#xff0c;包括…

[ritsec CTF 2024] 密码部分

这个比较密码这块还是比较简单的&#xff0c;经过问了N人以后终于完成。 [Warm Up] Words 给了个猪圈密码的图片&#xff0c;这东西好久不见的感觉。 [Warm Up] Emails MTP似乎也没多好的方法&#xff0c;猜更快&#xff0c;先给了几封email然后一个用MTP长度是32&#xff08…