作者推荐
本文涉及知识点
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;
};
