【动态规划】【前缀和】【推荐】2463. 最小移动总距离

作者推荐

【广度优先搜索】【网格】【割点】【 推荐】1263. 推箱子

本文涉及知识点

动态规划汇总
C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频

2463. 最小移动总距离

X 轴上有一些机器人和工厂。给你一个整数数组 robot ，其中 robot[i] 是第 i 个机器人的位置。再给你一个二维整数数组 factory ，其中 factory[j] = [positionj, limitj] ，表示第 j 个工厂的位置在 positionj ，且第 j 个工厂最多可以修理 limitj 个机器人。
每个机器人所在的位置 互不相同 。每个工厂所在的位置也 互不相同 。注意一个机器人可能一开始跟一个工厂在 相同的位置 。
所有机器人一开始都是坏的，他们会沿着设定的方向一直移动。设定的方向要么是 X 轴的正方向，要么是 X 轴的负方向。当一个机器人经过一个没达到上限的工厂时，这个工厂会维修这个机器人，且机器人停止移动。
任何时刻，你都可以设置 部分 机器人的移动方向。你的目标是最小化所有机器人总的移动距离。
请你返回所有机器人移动的最小总距离。测试数据保证所有机器人都可以被维修。
注意：
所有机器人移动速度相同。
如果两个机器人移动方向相同，它们永远不会碰撞。
如果两个机器人迎面相遇，它们也不会碰撞，它们彼此之间会擦肩而过。
如果一个机器人经过了一个已经达到上限的工厂，机器人会当作工厂不存在，继续移动。
机器人从位置 x 到位置 y 的移动距离为 |y - x| 。
示例 1：
输入：robot = [0,4,6], factory = [[2,2],[6,2]]
输出：4
解释：如上图所示：

  • 第一个机器人从位置 0 沿着正方向移动，在第一个工厂处维修。
  • 第二个机器人从位置 4 沿着负方向移动，在第一个工厂处维修。
  • 第三个机器人在位置 6 被第二个工厂维修，它不需要移动。
    第一个工厂的维修上限是 2 ，它维修了 2 个机器人。
    第二个工厂的维修上限是 2 ，它维修了 1 个机器人。
    总移动距离是 |2 - 0| + |2 - 4| + |6 - 6| = 4 。没有办法得到比 4 更少的总移动距离。
    示例 2：
    输入：robot = [1,-1], factory = [[-2,1],[2,1]]
    输出：2
    解释：如上图所示：
  • 第一个机器人从位置 1 沿着正方向移动，在第二个工厂处维修。
  • 第二个机器人在位置 -1 沿着负方向移动，在第一个工厂处维修。
    第一个工厂的维修上限是 1 ，它维修了 1 个机器人。
    第二个工厂的维修上限是 1 ，它维修了 1 个机器人。
    总移动距离是 |2 - 1| + |(-2) - (-1)| = 2 。没有办法得到比 2 更少的总移动距离。
    提示：
    1 <= robot.length, factory.length <= 100
    factory[j].length == 2
    -109 <= robot[i], positionj <= 109
    0 <= limitj <= robot.length
    测试数据保证所有机器人都可以被维修。

动态规划

原理

性质一：r1和r2是两个机器人位置，且r1 < r2。令f1和r2是两个工厂位置，且f1 < f2。 选择一：f1修r1，f2修r2。选择二：f1修r2,f2修f1。方式一不劣于方式二。
下面分情况证明：
一，r2 <= f1。两个机器人都在左边，两种选择结果一样。可以这样理解，两个机器人都进f1，然后其中一个去f2。
二,r1 >= f2。两个机器人都在右边。两种选择结果一样。可以这样理解：两个机器人都近f2，然后其中一个去f1。
三，f1 < r1 < r2 < f2。绿线是选择一，红线是选择二。在这里插入图片描述
四，r1 < f1 f1 < r2 < f2 。
在这里插入图片描述
五，r1 < f1 r2 > f2。

在这里插入图片描述
六，f1<r1<f2 r2<r2。和情况四对称。

动态规划的状态表示

dp[i][j] 前i个工厂修理前j个机器人的最小移动距离。

动态规划的转移方程

最左边的i个工厂，修理了j个机器人，最后一个工厂修理了k个机器人。根据性质一，则这k个机器人一定是j个机器人中最右边的。
dp[i][j] = m i n k : 0 m i n ( l i m i t [ i ] , j ) \Large min_{k:0}^{min(limit[i],j)} mink:0min(limit[i],j)​ (pre[i-1][j-k])+移动k个机器人的总距离
左移的机器人和右移的机器人，分别利用前缀和计算总距离。先对机器人和工厂的位置排序，坐标小于等于工厂坐标机器人右移：
∑ 移动的机器人 ( 工厂到原点距离 − 机器人到原点的距离 ) → \sum _{移动的机器人} (工厂到原点距离-机器人到原点的距离) \rightarrow 移动的机器人∑​(工厂到原点距离−机器人到原点的距离)→ 工厂到原点的距离 ⋆ 移动的机器人数 − ∑ 移动的机器人 ( 机器人到原点的距离 ) 工厂到原点的距离\star 移动的机器人数 - \sum _{移动的机器人}(机器人到原点的距离) 工厂到原点的距离⋆移动的机器人数−移动的机器人∑​(机器人到原点的距离)

动态规划的初始值

dp[0][0]=0 其它3e11

动态规划的填表顺序

从左到右计算后置状态。

返回值

dp.back().back()

注意：
前缀和记录的是相对位置：坐标是负数也可以。

代码

核心代码

template<class ELE,class ELE2>
void MinSelf(ELE* seft, const ELE2& other)
{*seft = min(*seft,(ELE) other);
}template<class ELE>
void MaxSelf(ELE* seft, const ELE& other)
{*seft = max(*seft, other);
}template<class T = long long >
class CPreSum
{
public:CPreSum(const vector<int>& nums){m_data.push_back(0);for (int i = 0; i < nums.size(); i++){m_data.push_back(m_data[i] + nums[i]);}}template<class _PR>CPreSum(int iSize, _PR pr){m_data.push_back(0);for (int i = 0; i < iSize; i++){m_data.push_back(m_data[i] + pr(i));}}T Sum(int left, int rightExclu)const{return m_data[rightExclu] - m_data[left];}
protected:vector<T> m_data;
};class Solution {
public:long long minimumTotalDistance(vector<int>& robot, vector<vector<int>>& factory) {sort(robot.begin(), robot.end());sort(factory.begin(), factory.end(), [&factory](auto& v1,auto& v2) {return v1[0] <v2[0]; });int n1 = factory.size(), n2 = robot.size();vector<int> vLeftCount;for (int i = 0, j = 0; i < n1; i++){while ((j < n2) && (robot[j] <= factory[i][0])){j++;}vLeftCount.emplace_back(j);}CPreSum preSum(robot);vector<vector<long long>> dp(n1 + 1, vector<long long>(n2 + 1,3e11));dp[0][0] = 0;for (int i = 1; i <= n1; i++){dp[i][0] = 0;for (int j = 1; j <= n2; j++){for (int k = 0; k <= min(j, factory[i - 1][1]); k++){const long long iLefttMove = min(k,max(0, j - vLeftCount[i - 1]));const long long llRightMove = k - iLefttMove;long long llMove = preSum.Sum(j - iLefttMove, j) - iLefttMove * factory[i - 1][0];//左移llMove += factory[i - 1][0] * llRightMove - preSum.Sum(j-k,j-k+llRightMove);MinSelf(&dp[i][j], dp[i - 1][j - k] + llMove);}}}return dp.back().back();}	
};

核心代码

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> robot;vector<vector<int>> factory;{Solution sln;robot = { 0,4,6 }, factory = { {2,2},{6,2} };auto res = sln.minimumTotalDistance(robot,factory);Assert(res,4LL);}{Solution sln;robot = { 1,-1 }, factory = { {-2,1},{2,1} };auto res = sln.minimumTotalDistance(robot, factory);Assert(res, 2LL);}{Solution sln;robot = { 0,4,6 }, factory = { {-2,2},{-6,2} };auto res = sln.minimumTotalDistance(robot, factory);Assert(res, 20LL);}}

2023年2月

class Solution {
public:
long long minimumTotalDistance(vector& robot, vector<vector>& factory) {
m_c = robot.size();
std::sort(robot.begin(), robot.end());
std::sort(factory.begin(), factory.end(), [](const vector& v0, const vector& v1)
{
return v0[0] < v1[0];
});
vector vPre(m_c + 1, m_llNotMay);
vPre[0] = 0;
for (const auto& v : factory)
{
vector dp = vPre;
for (int i = 0; i < m_c; i++)
{
if (m_llNotMay == vPre[i])
{
continue;
}
long long llMove = 0;
for (int j = 1; j <= v[1]; j++)
{
if (i + j > m_c)
{
break;
}
llMove += abs(v[0] - robot[i + j - 1]);
dp[i + j] = min(dp[i + j], vPre[i] + llMove);
}
}
vPre.swap(dp);
}
return vPre[m_c];
}
int m_c;
const long long m_llNotMay = ((long long)INT_MAX) * 1000;
};

2023年8月

class Solution {
public:
long long minimumTotalDistance(vector& robot, vector<vector>& factory) {
m_c = robot.size();
std::sort(robot.begin(), robot.end());
std::sort(factory.begin(), factory.end(), [](const vector& v1, const vector& v2)
{return v1[0] < v2[0]; });
vector vPre(m_c + 1, m_llNotMay);//vPre[i] 当前工厂及更早工厂修理i个机器人的最小移动距离
vPre[0] = 0;
for (const auto& v : factory)
{
vector dp = vPre;//本工厂不修理机器人
for (int pre = 0; pre < m_c; pre++)
{
long long llMove = 0;
for (int iDo = 1; iDo <= v[1]; iDo++)
{
const int next = pre + iDo;
if (next > m_c)
{
break;
}
llMove += abs(robot[next-1] - v[0]);
dp[next] = min(dp[next], vPre[pre] + llMove);
}
}
vPre.swap(dp);
}
return vPre.back();
}
int m_c;
const long long m_llNotMay = 1e12;
};

2023年9月

class Solution {
public:
long long minimumTotalDistance(vector& robot, vector<vector>& factory) {
sort(robot.begin(), robot.end());
sort(factory.begin(), factory.end(), [](const vector& v1, const vector& v2)
{
return v1[0] < v2[0];
});
long long llMinPos = min(*robot.begin(),(*factory.begin())[0]);
vector vPreSumDis(1);
for (const auto& n : robot)
{
vPreSumDis.emplace_back(vPreSumDis.back() + n- llMinPos);
}
vector pre(1);//pre[i] 当前站点之前的站点修改i个机器人的最小成本
int iRight = 0;//当前工厂右边的第一个机器人
for (int i = 0; i < factory.size(); i++)
{
const int iFactoryPos = factory[i][0];
for (; (iRight < robot.size()) && (robot[iRight] <= iFactoryPos); iRight++);
const int iSize = min(robot.size(), pre.size()-1 + factory[i][1]);
vector dp(iSize+1,1e12);
for (int j = 0; j<pre.size(); j++)
{
for (int k = 0; (k <= factory[i][1])&&(j+k <= robot.size()); k++)
{//[j,iRight)个机器上右移[iRight,j+k)个机器人左右移
const long long llMove = MoveRight(j, min(j + k, iRight), iFactoryPos, llMinPos, vPreSumDis)+
MoveLeft(max(j,iRight),j+k, iFactoryPos, llMinPos, vPreSumDis);
dp[j + k] = min(dp[j + k], llMove+pre[j]);
}
}
pre.swap(dp);
}
return pre.back();
}
long long MoveRight(int left, int right,const int iFactoryPos,const long long llMinPos, const vector& vPreSumDis)
{
if (right <= left )
{
return 0;
}
return (long long)(right - left) * (iFactoryPos - llMinPos) - (vPreSumDis[right] - vPreSumDis[left]);
}
long long MoveLeft(int left, int right, const int iFactoryPos, const long long llMinPos, const vector& vPreSumDis)
{
if (right <= left)
{
return 0;
}
return vPreSumDis[right] - vPreSumDis[left] - (long long)(right - left) * (iFactoryPos - llMinPos);
}
};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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++**实现。

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

如若内容造成侵权/违法违规/事实不符，请联系瞎胡闹网进行投诉反馈，一经查实，立即删除！

相关文章

2.5G/5G/10G高速率网络变压器（网络隔离变压器）产品介绍（1）

2.5G/5G/10G高速率网络变压器（网络隔离变压器）产品介绍（1）

Hqst华轩盛(石门盈盛)电子导读&#xff1a;高速率/2.5G 的带POE插件&#xff08;DIP&#xff09;款千兆双口网络变压器2G54801DP特点 一 ﹑2.5G高速率网络变压器&#xff08;网络隔离变压器&#xff09;&#xff1a;2G54801DP外观与尺寸 2G54801DP这颗产品尺寸为&#xff1a;长…
阅读更多...
备战蓝桥杯————双指针技巧巧解数组2

备战蓝桥杯————双指针技巧巧解数组2

利用双指针技巧来解决七道与数组相关的题目。 两数之和 II - 输入有序数组&#xff1a; 给定一个按升序排列的数组&#xff0c;找到两个数使它们的和等于目标值。可以使用双指针技巧&#xff0c;在数组两端设置左右指针&#xff0c;根据两数之和与目标值的大小关系移动指针。 …
阅读更多...
测试计划、测试方案、测试策略、测试用例的区别

测试计划、测试方案、测试策略、测试用例的区别

一 测试计划 测试计划是指描述了要进行的测试活动的范围、方法、资源和进度的文档。它主要包括测试项、被测特性、各阶段的测试任务、时间进度安排&#xff0c;谁执行任务和风险控制等&#xff0c;可以包括测试策略。 二 测试方案 测试方案是指描述需要测试的特性、测试的方…
阅读更多...
MT8791迅鲲900T联发科5G安卓核心板规格参数_MTK平台方案定制

MT8791迅鲲900T联发科5G安卓核心板规格参数_MTK平台方案定制

MT8791安卓核心板是一款搭载了旗舰级配置的中端手机芯片。该核心板采用了八核CPU架构设计&#xff0c;但是升级了旗舰级的Arm Cortex-A78核心&#xff0c;两个大核主频最高可达2.4GHz。配备了Arm Mali-G68 GPU&#xff0c;通过Mali-G88的先进技术&#xff0c;图形处理性能大幅提…
阅读更多...
如何查看电脑使用记录？保障个人隐私和安全

如何查看电脑使用记录？保障个人隐私和安全

查看电脑使用记录是了解电脑活动的一种重要方式&#xff0c;可以帮助用户追踪应用程序的使用情况、登录和关机时间、文件的访问记录等。在本文中&#xff0c;我们将介绍如何查看电脑使用记录的三个方法&#xff0c;以分步骤详细说明如何查看电脑使用记录&#xff0c;帮助用户更…
阅读更多...
Jenkins中Publish Over SSH插件使用（1）

Jenkins中Publish Over SSH插件使用（1）

SSH插件 前言Publish Over SSH插件是jenkins里面必不可少的插件之一&#xff0c;主要的功能有两个把jenkins服务器上的文件&#xff0c;传输到远程nginx&#xff0c; 远程执行shell命令和脚本。 1. SSH插件下载与配置 1.1 下载Publish over SSH插件 系统管理—》管理插件 …
阅读更多...
数据存储-文件存储

数据存储-文件存储

一、CSV文件存储 csv是python的标准库 import csvheader [班级, 姓名, 性别, 手机号, QQ]# 二维数组 rows [[学习一班, 大娃, 男, a130111111122, 987456123],[学习二班, 二娃, 女, a130111111123, 987456155],[学习三班, 三娃, 男, a130111111124, 987456123], ]f open(r…
阅读更多...
springboot邮箱注册

springboot邮箱注册

1.准备工作 操作之前准备两个邮箱 我准备了网易邮箱和QQ邮箱&#xff0c;网易邮箱用来发送验证码&#xff0c;QQ邮箱用来做注册&#xff08;希望大家和我一样&#xff0c;不然可能会出错 &#xff09; 发送验证码的邮箱需要开启一些设置&#xff0c;否则不…
阅读更多...
小程序画布（二维地图线）

小程序画布（二维地图线）

首先开始是想用小程序兼容openlayers的&#xff0c;但是了解到用不了&#xff0c;那就用画布来解决 实际效果如下 wxml中代码 <canvas id"trackDesignCanvas" //指定 id 的 Canvas 组件class"orbit-canvas-main" type"2d" …
阅读更多...
C++之deque

C++之deque

一、vector与list的优缺点 vector的优点&#xff1a;下标的随机访问&#xff0c;尾插&#xff0c;尾删效率高。CPU高速缓存命中率高vector的缺点&#xff1a;扩容(效率&#xff0c;空间浪费)&#xff0c;不适合头插头删。 连续的物理空间为他带来了优点也带来了缺点&#xff0c…
阅读更多...
C++入门学习（三十六）函数的声明

C++入门学习（三十六）函数的声明

程序是自上而下运行的&#xff0c;比如我下面的代码&#xff1a; #include <iostream> #include<string> using namespace std;int main() { int a1; int b2;int sumaddNumbers(a,b); cout<<sum;return 0; }int addNumbers(int a, int b) { int sum …
阅读更多...
2.23数据结构

2.23数据结构

单向循环链表 创建单向循环链表&#xff0c;创建节点 &#xff0c;头插&#xff0c;按位置插入&#xff0c;输出&#xff0c;尾删&#xff0c;按位置删除功能 //main.c #include "loop_list.h" int main() {loop_p Hcreate_head();insert_head(H,12);insert_head(…
阅读更多...
基于Mapbox展示GDAL处理的3D行政区划展示实践

基于Mapbox展示GDAL处理的3D行政区划展示实践

目录 前言 一、Gdal数据处理 1、数据展示 2、Java数据转换 二、Mapbox可视化 1、定义Mapbox地图 2、地图初始化 3、创建地图 三、界面优化 1、区域颜色设置 2、高度自适应和边界区分 3、中文标注 总结 前言 最近有遇到一个需求&#xff0c;用户想在地图上把行政区划…
阅读更多...
【新书推荐】8.1 数据传送指令

【新书推荐】8.1 数据传送指令

第八章 8086指令系统 我们把汇编指令称为机器语言的指令助记符&#xff0c;每一条汇编指令都对应一条机器指令。X86 CPU厂商AMD和INTEL提供硬编码表。编译器或者调试器就是通过查表的方式&#xff0c;将汇编指令翻译成机器指令&#xff0c;或者将机器指令反编译成汇编指令。 …
阅读更多...
matplotlib绘图初步

matplotlib绘图初步

文章目录 绘制曲线图完整流程图像属性 绘制曲线图 matplotlib是python中最常用的可视化库&#xff0c;提供了不同坐标系下的二十余种常用图像&#xff0c;并且提供了动态图像绘制的方法&#xff0c;可以满足科学计算中的绝大多数可视化需求。而在matplotlib中&#xff0c;绝大…
阅读更多...
RM电控讲义【HAL库篇】（二）

RM电控讲义【HAL库篇】（二）

8080并口模式是一种常见的计算机接口模式&#xff0c;主要用于LCD&#xff08;液晶显示屏&#xff09;模块。 在8080并口模式中&#xff0c;通信端口包括多种信号线&#xff0c;用于实现数据的读写和控制功能。主要的信号线包括&#xff1a; CS&#xff08;片选信号&#xff…
阅读更多...
【开源】JAVA+Vue.js实现大病保险管理系统

【开源】JAVA+Vue.js实现大病保险管理系统

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 系统配置维护2.2 系统参保管理2.3 大病保险管理2.4 大病登记管理2.5 保险审核管理 三、系统详细设计3.1 系统整体配置功能设计3.2 大病人员模块设计3.3 大病保险模块设计3.4 大病登记模块设计3.5 保险审核模块设计 四、…
阅读更多...
【Linux】 yum命令使用

【Linux】 yum命令使用

yum命令 yum&#xff08; Yellow dog Updater, Modified&#xff09; 是一个在 Fedora、CentOS 及其它一些基于 RPM 的 Linux 发行版中使用的包管理器。它允许用户自动安装、更新、配置和删除软件包。yum 由 Python 写成&#xff0c;基于 RPM&#xff08;Red Hat Package Mana…
阅读更多...
端口占用：Web server failed to start. Port XXX was already in use.原因分析-解决方案

端口占用：Web server failed to start. Port XXX was already in use.原因分析-解决方案

一、windows 1.Web server failed to start. Port XXX was already in use出错原因分析 端口被占用了&#xff0c;我们只需要换一个端口就可以了&#xff0c;如果就想要用特定的端口&#xff0c;我们需要使用下面的命令&#xff0c;先找到对应端口号的进程号&#xff0c;然后结…
阅读更多...
面试经典150题 -- 二叉树搜索树 (总结)

面试经典150题 -- 二叉树搜索树 (总结)

总的链接 : https://leetcode.cn/studyplan/top-interview-150/ 二叉搜索树相关概念 : 二叉搜索树是一个有序树。 若它的左子树不空&#xff0c;则左子树上所有结点的值均小于它的根结点的值&#xff1b;若它的右子树不空&#xff0c;则右子树上所有结点的值均大于它的根结…
阅读更多...
最新文章

Copyright @ 2022~2023