作者推荐
【动态规划】【状态压缩】【2次选择】【广度搜索】1494. 并行课程 II
本文涉及知识点
LeetCode:1883. 准时抵达会议现场的最小跳过休息次数
给你一个整数 hoursBefore ，表示你要前往会议所剩下的可用小时数。要想成功抵达会议现场，你必须途经 n 条道路。道路的长度用一个长度为 n 的整数数组 dist 表示，其中 dist[i] 表示第 i 条道路的长度（单位：千米）。另给你一个整数 speed ，表示你在道路上前进的速度（单位：千米每小时）。
当你通过第 i 条路之后，就必须休息并等待，直到 下一个整数小时 才能开始继续通过下一条道路。注意：你不需要在通过最后一条道路后休息，因为那时你已经抵达会议现场。
例如，如果你通过一条道路用去 1.4 小时，那你必须停下来等待，到 2 小时才可以继续通过下一条道路。如果通过一条道路恰好用去 2 小时，就无需等待，可以直接继续。
然而，为了能准时到达，你可以选择 跳过 一些路的休息时间，这意味着你不必等待下一个整数小时。注意，这意味着与不跳过任何休息时间相比，你可能在不同时刻到达接下来的道路。
例如，假设通过第 1 条道路用去 1.4 小时，且通过第 2 条道路用去 0.6 小时。跳过第 1 条道路的休息时间意味着你将会在恰好 2 小时完成通过第 2 条道路，且你能够立即开始通过第 3 条道路。
返回准时抵达会议现场所需要的 最小跳过次数 ，如果 无法准时参会 ，返回 -1 。
示例 1：
输入：dist = [1,3,2], speed = 4, hoursBefore = 2
输出：1
解释：
不跳过任何休息时间，你将用 (1/4 + 3/4) + (3/4 + 1/4) + (2/4) = 2.5 小时才能抵达会议现场。
可以跳过第 1 次休息时间，共用 ((1/4 + 0) + (3/4 + 0)) + (2/4) = 1.5 小时抵达会议现场。
注意，第 2 次休息时间缩短为 0 ，由于跳过第 1 次休息时间，你是在整数小时处完成通过第 2 条道路。
示例 2：
输入：dist = [7,3,5,5], speed = 2, hoursBefore = 10
输出：2
解释：
不跳过任何休息时间，你将用 (7/2 + 1/2) + (3/2 + 1/2) + (5/2 + 1/2) + (5/2) = 11.5 小时才能抵达会议现场。
可以跳过第 1 次和第 3 次休息时间，共用 ((7/2 + 0) + (3/2 + 0)) + ((5/2 + 0) + (5/2)) = 10 小时抵达会议现场。
示例 3：
输入：dist = [7,3,5,5], speed = 1, hoursBefore = 10
输出：-1
解释：即使跳过所有的休息时间，也无法准时参加会议。
提示：
n == dist.length
1 <= n <= 1000
1 <= dist[i] <= 105
1 <= speed <= 106
1 <= hoursBefore <= 107
动态规划
动态规划的状态
pre[j] 表示 跳过j次，行驶前i条道路的最少时间。
dp[j] 表示 跳过j次，行驶前i+1条道路的最少时间。
不直接记录时间，那样会有小数。 记录：时间*speed 这样就是整数。
动态规划的转移方程
0 == pre[j]%speed 刚好是整数数据，无需跳过。
dp[j] =min( pre[j] + dist[i]
否则：
{ d p [ j + 1 ] = m i n ( , p r e [ j ] + d i s t [ i ] ) 跳过 d p [ j ] = m i n ( , p r e [ j ] / s p e e d ∗ s p e e d + s p e e d + d i s t [ i ] ) 不跳过 \begin{cases} dp[j+1] = min(,pre[j]+dist[i]) & 跳过 \\ dp[j] = min(,pre[j]/speed*speed + speed + dist[i]) & 不跳过\\ \end{cases}{dp[j+1]=min(,pre[j]+dist[i])dp[j]=min(,pre[j]/speed∗speed+speed+dist[i])跳过不跳过
动态规划的初始状态
pre全为0。前置状态转移后置状态。
动态规划的转移方程
i从0到大。
动态规划的返回值
pre第一个小于等于hoursBefore 的下标。
代码
核心代码
class Solution { public: int minSkips(vector<int>& dist, int speed, int hoursBefore) { m_c = dist.size(); vector<int> pre(m_c + 1); for (const auto& d : dist) { vector<int> dp(m_c + 1, m_iNotMay); for (int j = 0; j <= m_c; j++) { if (0 == pre[j] % speed) { dp[j] = min(dp[j], pre[j] + d); continue; } dp[j] = min(dp[j], pre[j] / speed * speed + speed + d);//不跳过 if (j != m_c) { dp[j+1] = min(dp[j+1], pre[j] + d); } } pre.swap(dp); } for (int i = 0; i < pre.size(); i++) { if (pre[i] <= (long long)hoursBefore * speed) { return i; } } return -1; } int m_c; const int m_iNotMay = 2000'000'000; };
测试用例
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> dist; int speed, hoursBefore; { Solution sln; dist = { 1, 3, 2 }, speed = 4, hoursBefore = 2; auto res = sln.minSkips(dist, speed, hoursBefore); Assert(res,1); } { Solution sln; dist = { 7, 3, 5, 5 }, speed = 1, hoursBefore = 10; auto res = sln.minSkips(dist, speed, hoursBefore); Assert(res, -1); } }
2023年2月
class Solution {
public:
int minSkips(vector& dist, int speed, int hoursBefore) {
m_c = dist.size();
vector pre(m_c + 1, m_iNotMay);
pre[0] = 0;
for (const auto& i : dist)
{
vector dp(m_c + 1, m_iNotMay);
const double dCurTime = ((double)i) / speed;
for (int j = 0; j < m_c; j++)
{
if (pre[j] >= m_iNotMay + m_eps)
{
continue;
}
dp[j] = min(dp[j], ceil(pre[j] - m_eps) + dCurTime);
dp[j + 1] = min(dp[j + 1], pre[j] + dCurTime);
}
pre.swap(dp);
}
for (int i = 0; i < pre.size(); i++)
{
if (pre[i] <= hoursBefore + m_eps)
{
return i;
}
}
return -1;
}
int m_c;
int m_iNotMay = 1000 * 1000 * 1000;
const double m_eps = 1E-7;
};
2023年2月第二版
class Solution {
public:
int minSkips(vector& dist, int speed, int hoursBefore) {
m_c = dist.size();
vector iiDists;
for (const auto& i : dist)
{
iiDists.push_back((long long)i * speed);
}
vector pre(m_c + 1, m_iNotMay);
pre[0] = 0;
for (const auto& i : iiDists)
{
vector dp(m_c + 1, m_iNotMay);
const long long llCurTime = i / speed;
for (int j = 0; j < m_c; j++)
{
if (pre[j] >= m_iNotMay )
{
continue;
}
const long long llNew = (0 == pre[j] % speed) ? pre[j] : (speed * (pre[j] / speed + 1));
dp[j] = min(dp[j], llNew + llCurTime);
dp[j + 1] = min(dp[j + 1], pre[j] + llCurTime);
}
pre.swap(dp);
}
for (int i = 0; i < pre.size(); i++)
{
if (pre[i] <= hoursBefore*(long long) speed )
{
return i;
}
}
return -1;
}
int m_c;
long long m_iNotMay = 1000LL * 1000 * 100010001000;
};
