【动态规划】【C++算法】2188. 完成比赛的最少时间

2024-02-09 21:04
文章标签 算法 动态 规划 c++ 最少 时间 完成 比赛 2188

本文主要是介绍【动态规划】【C++算法】2188. 完成比赛的最少时间，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

作者推荐

【动态规划】【前缀和】【C++算法】LCP 57. 打地鼠

本文涉及知识点

动态规划汇总

LeetCode2188. 完成比赛的最少时间

给你一个下标从 0 开始的二维整数数组 tires ，其中 tires[i] = [fi, ri] 表示第 i 种轮胎如果连续使用，第 x 圈需要耗时 fi * ri(x-1) 秒。
比方说，如果 fi = 3 且 ri = 2 ，且一直使用这种类型的同一条轮胎，那么该轮胎完成第 1 圈赛道耗时 3 秒，完成第 2 圈耗时 3 * 2 = 6 秒，完成第 3 圈耗时 3 * 22 = 12 秒，依次类推。
同时给你一个整数 changeTime 和一个整数 numLaps 。
比赛总共包含 numLaps 圈，你可以选择 任意 一种轮胎开始比赛。每一种轮胎都有 无数条 。每一圈后，你可以选择耗费 changeTime 秒 换成 任意一种轮胎（也可以换成当前种类的新轮胎）。
请你返回完成比赛需要耗费的 最少 时间。
示例 1：
输入：tires = [[2,3],[3,4]], changeTime = 5, numLaps = 4
输出：21
解释：
第 1 圈：使用轮胎 0 ，耗时 2 秒。
第 2 圈：继续使用轮胎 0 ，耗时 2 * 3 = 6 秒。
第 3 圈：耗费 5 秒换一条新的轮胎 0 ，然后耗时 2 秒完成这一圈。
第 4 圈：继续使用轮胎 0 ，耗时 2 * 3 = 6 秒。
总耗时 = 2 + 6 + 5 + 2 + 6 = 21 秒。
完成比赛的最少时间为 21 秒。
示例 2：
输入：tires = [[1,10],[2,2],[3,4]], changeTime = 6, numLaps = 5
输出：25
解释：
第 1 圈：使用轮胎 1 ，耗时 2 秒。
第 2 圈：继续使用轮胎 1 ，耗时 2 * 2 = 4 秒。
第 3 圈：耗时 6 秒换一条新的轮胎 1 ，然后耗时 2 秒完成这一圈。
第 4 圈：继续使用轮胎 1 ，耗时 2 * 2 = 4 秒。
第 5 圈：耗时 6 秒换成轮胎 0 ，然后耗时 1 秒完成这一圈。
总耗时 = 2 + 4 + 6 + 2 + 4 + 6 + 1 = 25 秒。
完成比赛的最少时间为 25 秒。
提示：
1 <= tires.length <= 105
tires[i].length == 2
1 <= fi, changeTime <= 105
2 <= ri <= 105
1 <= numLaps <= 1000

动态规划

ri大于2，就算fi为1。20圈后，用时就大于等于10^6，不如：换新轮胎只跑一圈。
一个轮胎跑i圈，只需要考虑用时最短的那种轮胎。
轮胎+圈数只需要考虑不到20种状态。

动态规划的状态表示

dp[j] 使用前i+1种状态需要的最少时间，包括换轮胎的时间。
时间复杂度：O(numLaps 20)

动态规划的转移方程

dp[j+i] = min(,dp[j]+useTime)

动态规划的初始值

dp[0] = 0，其它1e9。

动态规划的填表顺序

依次处理不到20种状态。

动态规划的返回值

dp.back()-changeTime

代码

核心代码

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);
}class Solution {
public:int minimumFinishTime(vector<vector<int>>& tires, int changeTime, int numLaps) {		vector<long long> vCurTireTime;for (const auto& v : tires){	vCurTireTime.emplace_back(v[0]);}auto vTotalTireTime = vCurTireTime;vector<long long> useTime = { 0,*std::min_element(vCurTireTime.begin(),vCurTireTime.end()) };for(int q = 2; q <= numLaps ;q++ ){for (int i = 0 ; i < vCurTireTime.size();i++ ){vCurTireTime[i] *= tires[i][1];MinSelf(&vCurTireTime[i], m_llNotMay);vTotalTireTime[i] += vCurTireTime[i];MinSelf(&vTotalTireTime[i], m_llNotMay);}const long long llMin = *std::min_element(vTotalTireTime.begin(), vTotalTireTime.end());if (llMin >= (useTime[1] + changeTime) * q){break;}useTime.emplace_back(llMin);}vector<long long> dp(numLaps + 1, m_llNotMay);dp[0] = 0;for (int i = 1; i < useTime.size(); i++){for (int pre = 0; pre < dp.size(); pre++){const int cur = pre + i;if (cur < dp.size()){MinSelf(&dp[cur], dp[pre] + useTime[i] + changeTime);}}}return (int)(dp.back()-changeTime);}const long long m_llNotMay = 2e9;
};

测试用例

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<vector<int>> tires;int changeTime, numLaps;{Solution sln;tires = { {2,3},{3,4} }, changeTime = 5, numLaps = 4;auto res = sln.minimumFinishTime(tires, changeTime, numLaps);Assert(res,21);}{Solution sln;tires = { {1,10},{2,2},{3,4} }, changeTime = 6, numLaps = 5;auto res = sln.minimumFinishTime(tires, changeTime, numLaps);Assert(res, 25);}{Solution sln;tires = { {100000, 2}, { 10000,10000 }, { 1,2 }, { 1,10000 } }, changeTime = 10000, numLaps = 1000;auto res = sln.minimumFinishTime(tires, changeTime, numLaps);Assert(res, 1085253);}{Solution sln;tires = { {100000,2},{10000,10000},{1,2},{1,10000} }, changeTime = 1, numLaps = 1;auto res = sln.minimumFinishTime(tires, changeTime, numLaps);Assert(res, 1);}}

2023年2月

class Solution {
public:
int minimumFinishTime(vector<vector>& tires, int changeTime, int numLaps) {
m_vNumLapUseMinTime.resize(20, m_iNotMay);
for (const auto& v : tires)
{
long long iNeedTime = v[0];
int iPre = 0;
for (int j = 0; j < 20; j++)
{
if (0 != j)
{
iNeedTime = iNeedTime*((long long)v[1]);
}
if (iNeedTime >= m_vNumLapUseMinTime[0] + changeTime)
{
break;
}
iPre += iNeedTime;
m_vNumLapUseMinTime[j] = min(m_vNumLapUseMinTime[j], (int)iPre);
}
}
int iVilidNum = 0;
for (const auto& i : m_vNumLapUseMinTime)
{
if (m_iNotMay != i)
{
iVilidNum++;
}
}
vector dp(numLaps + 1, m_iNotMay);
dp[0] = 0;
for (int preNumLaps = 0; preNumLaps < numLaps; preNumLaps++)
{
for (int j = 0; j < iVilidNum; j++) {
const int iNewNumLaps = preNumLaps + j + 1;
if (iNewNumLaps > numLaps)
{
continue;
}
dp[iNewNumLaps] = min(dp[iNewNumLaps], dp[preNumLaps] + m_vNumLapUseMinTime[j] + changeTime);
}
}
return dp[numLaps] - changeTime;
}
vector m_vNumLapUseMinTime;
const int m_iNotMay = 1000 * 1000 * 1000;
};

扩展阅读

视频课程

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

这篇关于【动态规划】【C++算法】2188. 完成比赛的最少时间的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/695283。

相关文章

C++11范围for初始化列表auto decltype详解

C++11范围for初始化列表auto decltype详解

《C++11范围for初始化列表autodecltype详解》C++11引入auto类型推导、decltype类型推断、统一列表初始化、范围for循环及智能指针,提升代码简洁性、类型安全与资源管理效... 目录C++11新特性1. 自动类型推导auto1.1 基本语法2. decltype3. 列表初始化3
阅读更多...
C++11右值引用与Lambda表达式的使用

C++11右值引用与Lambda表达式的使用

《C++11右值引用与Lambda表达式的使用》C++11引入右值引用,实现移动语义提升性能,支持资源转移与完美转发；同时引入Lambda表达式,简化匿名函数定义,通过捕获列表和参数列表灵活处理变量... 目录C++11新特性右值引用和移动语义左值 / 右值常见的左值和右值移动语义移动构造函数移动复制运算符
阅读更多...
Java获取当前时间String类型和Date类型方式

Java获取当前时间String类型和Date类型方式

《Java获取当前时间String类型和Date类型方式》：本文主要介绍Java获取当前时间String类型和Date类型方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录Java获取当前时间String和Date类型String类型和Date类型输出结果总结Java获取
阅读更多...
Python实现批量提取BLF文件时间戳

Python实现批量提取BLF文件时间戳

《Python实现批量提取BLF文件时间戳》BLF（BinaryLoggingFormat）作为Vector公司推出的CAN总线数据记录格式,被广泛用于存储车辆通信数据,本文将使用Python轻松提取... 目录一、为什么需要批量处理 BLF 文件二、核心代码解析：从文件遍历到数据导出1. 环境准备与依赖库
阅读更多...
go动态限制并发数量的实现示例

go动态限制并发数量的实现示例

《go动态限制并发数量的实现示例》本文主要介绍了Go并发控制方法,通过带缓冲通道和第三方库实现并发数量限制,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面... 目录带有缓冲大小的通道使用第三方库其他控制并发的方法因为go从语言层面支持并发，所以面试百分百会问到
阅读更多...
C++中detach的作用、使用场景及注意事项

C++中detach的作用、使用场景及注意事项

《C++中detach的作用、使用场景及注意事项》关于C++中的detach,它主要涉及多线程编程中的线程管理,理解detach的作用、使用场景以及注意事项,对于写出高效、安全的多线程程序至关重要,下... 目录一、什么是join()？它的作用是什么？类比一下：二、join()的作用总结三、join()怎么
阅读更多...
C++中全局变量和局部变量的区别

C++中全局变量和局部变量的区别

《C++中全局变量和局部变量的区别》本文主要介绍了C++中全局变量和局部变量的区别,全局变量和局部变量在作用域和生命周期上有显著的区别,下面就来介绍一下,感兴趣的可以了解一下... 目录一、全局变量定义生命周期存储位置代码示例输出二、局部变量定义生命周期存储位置代码示例输出三、全局变量和局部变量的区别作用域
阅读更多...
C++中assign函数的使用

C++中assign函数的使用

《C++中assign函数的使用》在C++标准模板库中,std::list等容器都提供了assign成员函数,它比操作符更灵活,支持多种初始化方式,下面就来介绍一下assign的用法,具有一定的参考价... 目录​1.assign的基本功能​​语法​2. 具体用法示例​​​(1) 填充n个相同值​​(2)
阅读更多...
c++ 类成员变量默认初始值的实现

c++ 类成员变量默认初始值的实现

《c++类成员变量默认初始值的实现》本文主要介绍了c++类成员变量默认初始值,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录C++类成员变量初始化c++类的变量的初始化在C++中，如果使用类成员变量时未给定其初始值，那么它将被
阅读更多...
C++中NULL与nullptr的区别小结

C++中NULL与nullptr的区别小结

《C++中NULL与nullptr的区别小结》本文介绍了C++编程中NULL与nullptr的区别,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编... 目录C++98空值——NULLC++11空值——nullptr区别对比示例 C++98空值——NUL
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2