【动态规划】【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;

};


目录
打赏
0
0
0
0
36
分享
相关文章
从集思录可转债数据探秘:Python与C++实现的移动平均算法应用
本文探讨了如何利用移动平均算法分析集思录提供的可转债数据,帮助投资者把握价格趋势。通过Python和C++两种编程语言实现简单移动平均(SMA),展示了数据处理的具体方法。Python代码借助`pandas`库轻松计算5日SMA,而C++代码则通过高效的数据处理展示了SMA的计算过程。集思录平台提供了详尽且及时的可转债数据,助力投资者结合算法与社区讨论,做出更明智的投资决策。掌握这些工具和技术,有助于在复杂多变的金融市场中挖掘更多价值。
22 12
员工屏幕监控系统之 C++ 图像差分算法
在现代企业管理中,员工屏幕监控系统至关重要。本文探讨了其中常用的图像差分算法,该算法通过比较相邻两帧图像的像素差异,检测屏幕内容变化,如应用程序切换等。文中提供了C++实现代码,并介绍了其在实时监控、异常行为检测和数据压缩等方面的应用,展示了其实现简单、效率高的特点。
27 15
|
30天前
|
【潜意识Java】蓝桥杯算法有关的动态规划求解背包问题
本文介绍了经典的0/1背包问题及其动态规划解法。
50 5
探秘:基于 C++ 的局域网电脑控制软件自适应指令分发算法
在现代企业信息化架构中,局域网电脑控制软件如同“指挥官”,通过自适应指令分发算法动态调整指令发送节奏与数据量,确保不同性能的终端设备高效运行。基于C++语言,利用套接字实现稳定连接和线程同步管理,结合实时状态反馈,优化指令分发策略,提升整体管控效率,保障网络稳定,助力数字化办公。
52 19
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
51 2
基于哈希表的文件共享平台 C++ 算法实现与分析
在数字化时代,文件共享平台不可或缺。本文探讨哈希表在文件共享中的应用,包括原理、优势及C++实现。哈希表通过键值对快速访问文件元数据(如文件名、大小、位置等),查找时间复杂度为O(1),显著提升查找速度和用户体验。代码示例展示了文件上传和搜索功能,实际应用中需解决哈希冲突、动态扩容和线程安全等问题,以优化性能。
基于红黑树的局域网上网行为控制C++ 算法解析
在当今网络环境中,局域网上网行为控制对企业和学校至关重要。本文探讨了一种基于红黑树数据结构的高效算法,用于管理用户的上网行为,如IP地址、上网时长、访问网站类别和流量使用情况。通过红黑树的自平衡特性,确保了高效的查找、插入和删除操作。文中提供了C++代码示例,展示了如何实现该算法,并强调其在网络管理中的应用价值。
|
2月前
|
用 C++ 算法控制员工上网的软件,关键逻辑是啥?来深度解读下
在企业信息化管理中,控制员工上网的软件成为保障网络秩序与提升办公效率的关键工具。该软件基于C++语言,融合红黑树、令牌桶和滑动窗口等算法,实现网址精准过滤、流量均衡分配及异常连接监测。通过高效的数据结构与算法设计,确保企业网络资源优化配置与安全防护升级,同时尊重员工权益,助力企业数字化发展。
65 4
|
3月前
|
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果;贪心算法在每一步选择局部最优解,追求全局最优;动态规划通过保存子问题的解,避免重复计算,确保全局最优。这三种算法各具特色,适用于不同类型的问题,合理选择能显著提升编程效率。
81 2
【C++篇】深度解析类与对象(下)
在上一篇博客中,我们学习了C++的基础类与对象概念,包括类的定义、对象的使用和构造函数的作用。在这一篇,我们将深入探讨C++类的一些重要特性,如构造函数的高级用法、类型转换、static成员、友元、内部类、匿名对象,以及对象拷贝优化等。这些内容可以帮助你更好地理解和应用面向对象编程的核心理念,提升代码的健壮性、灵活性和可维护性。
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等