Hard
题目描述
给定 n 个在基地营地的个体需要使用一艘船穿过河流到达目的地。船一次最多可以载 k 个人。旅程受到环境条件的影响，这些条件在 m 个阶段中周期性变化。
每个阶段 j 都有一个速度倍数 mul[j]：
- 如果 mul[j] > 1，旅程会减慢。
- 如果 mul[j] < 1，旅程会加速。
每个个体 i 都有一个划船强度，用 time[i] 表示，即他们在中性条件下独自渡河所需的时间（分钟）。
规则：
- 一个团体 g 在阶段 j 出发，渡河时间等于其成员中最大的 time[i]，乘以 mul[j] 分钟到达目的地。
- 团体在时间 d 内渡河后，阶段前进 floor(d) % m 步。
- 如果有个体被留下，必须有一个人带船返回。设 r 是返回人员的索引，返回需要 time[r] × mul[current_stage] 时间（定义为 return_time），阶段前进 floor(return_time) % m。
返回运输所有个体所需的最短总时间。如果无法将所有个体运输到目的地，返回 -1。
示例 1：
输入：n = 1, k = 1, m = 2, time = [5], mul = [1.0,1.3]
输出：5.00000
示例 2：
输入：n = 3, k = 2, m = 3, time = [2,5,8], mul = [1.0,1.5,0.75]
输出：14.50000
示例 3：
输入：n = 2, k = 1, m = 2, time = [10,10], mul = [2.0,2.0]
输出：-1.00000
约束条件：
- 1 <= n == time.length <= 12
- 1 <= k <= 5
- 1 <= m <= 5
- 1 <= time[i] <= 100
- m == mul.length
- 0.5 <= mul[i] <= 2.0
解题思路
这是一个复杂的动态规划问题，需要考虑状态转移和环境条件的周期性变化。
核心思路：
状态定义：使用位掩码
mask表示还在基地营地的人员集合，stage表示当前环境阶段。状态(mask, stage)表示当前配置下到达目的地所需的最短时间。不可能情况判断：当 k=1 且 n>1 时，无法完成任务，因为必须有人返回带船，但只能载一个人。
Dijkstra算法：将整个问题建模为图论问题，状态之间的转移作为边，使用Dijkstra算法求最短路径。
状态转移：
- 从当前状态选择最多 k 个人渡河
- 计算渡河时间（最慢者的时间 × 当前阶段倍数）
- 更新阶段（前进 floor(渡河时间) % m 步）
- 如果还有人留在基地，选择一个人返回
- 计算返回时间并再次更新阶段
优化策略：
- 使用优先队列确保按最短时间顺序处理状态
- 记忆化已访问状态避免重复计算
- 考虑不同的人员组合和返回人选择
算法复杂度主要取决于状态数量（2^n × m）和每个状态的转移数量。
代码实现
class Solution {
public:
double minTime(int n, int k, int m, vector<int>& time, vector<double>& mul) {
if (k == 1 && n > 1) return -1.0;
priority_queue<pair<double, pair<int, int>>,
vector<pair<double, pair<int, int>>>,
greater<pair<double, pair<int, int>>>> pq;
map<pair<int, int>, double> dist;
int startMask = (1 << n) - 1;
pq.push({0.0, {startMask, 0}});
dist[{startMask, 0}] = 0.0;
while (!pq.empty()) {
auto [d, state] = pq.top();
pq.pop();
int mask = state.first, stage = state.second;
if (mask == 0) return d;
if (dist.count({mask, stage}) && dist[{mask, stage}] < d) continue;
vector<int> people;
for (int i = 0; i < n; i++) {
if (mask & (1 << i)) people.push_back(i);
}
int sz = people.size();
for (int submask = 1; submask < (1 << sz) && __builtin_popcount(submask) <= k; submask++) {
vector<int> going;
for (int i = 0; i < sz; i++) {
if (submask & (1 << i)) going.push_back(people[i]);
}
int maxTime = 0;
for (int person : going) {
maxTime = max(maxTime, time[person]);
}
double crossTime = maxTime * mul[stage];
int newStage = (stage + ((int)crossTime) % m) % m;
int newMask = mask;
for (int person : going) {
newMask &= ~(1 << person);
}
if (newMask == 0) {
double totalTime = d + crossTime;
if (!dist.count({0, newStage}) || dist[{0, newStage}] > totalTime) {
dist[{0, newStage}] = totalTime;
pq.push({totalTime, {0, newStage}});
}
} else {
for (int returnPerson : going) {
double returnTime = time[returnPerson] * mul[newStage];
int finalStage = (newStage + ((int)returnTime) % m) % m;
int finalMask = newMask | (1 << returnPerson);
double totalTime = d + crossTime + returnTime;
if (!dist.count({finalMask, finalStage}) || dist[{finalMask, finalStage}] > totalTime) {
dist[{finalMask, finalStage}] = totalTime;
pq.push({totalTime, {finalMask, finalStage}});
}
}
}
}
}
return -1.0;
}
};
class Solution:
def minTime(self, n: int, k: int, m: int, time: List[int], mul: List[float]) -> float:
if k == 1 and n > 1:
return -1.0
import heapq
pq = [(0.0, (1 << n) - 1, 0)]
dist = {((1 << n) - 1, 0): 0.0}
while pq:
d, mask, stage = heapq.heappop(pq)
if mask == 0:
return d
if (mask, stage) in dist and dist[(mask, stage)] < d:
continue
people = [i for i in range(n) if mask & (1 << i)]
from itertools import combinations
for r in range(1, min(len(people), k) + 1):
for going in combinations(people, r):
max_time = max(time[person] for person in going)
cross_time = max_time * mul[stage]
new_stage = (stage + int(cross_time) % m) % m
new_mask = mask
for person in going:
new_mask &= ~(1 << person)
if new_mask == 0:
total_time = d + cross_time
if (0, new_stage) not in dist or dist[(0, new_stage)] > total_time:
dist[(0, new_stage)] = total_time
heapq.heappush(pq, (total_time, 0, new_stage))
else:
for return_person in going:
return_time = time[return_person] * mul[new_stage]
final_stage = (new_stage + int(return_time) % m) % m
final_mask = new_mask | (1 << return_person)
total_time = d + cross_time + return_time
if (final_mask, final_stage) not in dist or dist[(final_mask, final_stage)] > total_time:
dist[(final_mask, final_stage)] = total_time
heapq.heappush(pq, (total_time, final_mask, final_stage))
return -1.0
public class Solution {
public double MinTime(int n, int k, int m, int[] time, double[] mul) {
if (k == 1 && n > 1) return -1.0;
var pq = new PriorityQueue<(double dist, int mask, int stage), double>();
var dist = new Dictionary<(int, int), double>();
int startMask = (1 << n) - 1;
pq.Enqueue((0.0, startMask, 0), 0.0);
dist[(startMask, 0)] = 0.0;
while (pq.Count > 0) {
var (d, mask, stage) = pq.Dequeue();
if (mask == 0) return d;
if (dist.ContainsKey((mask, stage)) && dist[(mask, stage)] < d) continue;
var people = new List<int>();
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) != 0) people.Add(i);
}
int sz = people.Count;
for (int submask = 1; submask < (1 << sz) && BitOperations.PopCount((uint)submask) <= k; submask++) {
var going = new List<int>();
for (int i = 0; i < sz; i++) {
if ((submask & (1 << i)) != 0) going.Add(people[i]);
}
int maxTime = 0;
foreach (int person in going) {
maxTime = Math.Max(maxTime, time[person]);
}
double crossTime = maxTime * mul[stage];
int newStage = (stage + ((int)crossTime) % m) % m;
int newMask = mask;
foreach (int person in going) {
newMask &= ~(1 << person);
}
if (newMask == 0) {
double totalTime = d + crossTime;
if (!dist.ContainsKey((0, newStage)) || dist[(0, newStage)] > totalTime) {
dist[(0, newStage)] = totalTime;
pq.Enqueue((totalTime, 0, newStage), totalTime);
}
} else {
foreach (int returnPerson in going) {
double returnTime = time[returnPerson] * mul[newStage];
int finalStage = (newStage + ((int)returnTime) % m) % m;
int finalMask = newMask | (1 << returnPerson);
double totalTime = d + crossTime + returnTime;
if (!dist.ContainsKey((finalMask, finalStage)) || dist[(finalMask, finalStage)] > totalTime) {
dist[(finalMask, finalStage)] = totalTime;
pq.Enqueue((totalTime, finalMask, finalStage), totalTime);
}
}
}
}
}
return -1.0;
}
}
var minTime = function(n, k, m, time, mul) {
if (n > 1 && k === 1) return -1;
const memo = new Map();
function dfs(atBase, atDest, stage, totalTime) {
if (atBase.length === 0) return totalTime;
const key = `${atBase.sort().join(',')},${atDest.sort().join(',')},${stage}`;
if (memo.has(key)) return memo.get(key);
let minResult = Infinity;
// Try all combinations of sending k people
function getCombinations(arr, size) {
if (size > arr.length) return [];
if (size === 1) return arr.map(x => [x]);
if (size === arr.length) return [arr.slice()];
const result = [];
for (let i = 0; i < arr.length; i++) {
const rest = arr.slice(i + 1);
const smaller = getCombinations(rest, size - 1);
for (const combo of smaller) {
result.push([arr[i], ...combo]);
}
}
return result;
}
for (let sendSize = 1; sendSize <= Math.min(k, atBase.length); sendSize++) {
const combinations = getCombinations(atBase, sendSize);
for (const toSend of combinations) {
const maxTime = Math.max(...toSend.map(i => time[i]));
const crossTime = maxTime * mul[stage];
const newStage = (stage + Math.floor(crossTime)) % m;
const newAtBase = atBase.filter(x => !toSend.includes(x));
const newAtDest = [...atDest, ...toSend];
if (newAtBase.length === 0) {
minResult = Math.min(minResult, totalTime + crossTime);
} else {
// Someone must return
for (const returnPerson of toSend) {
const returnTime = time[returnPerson] * mul[newStage];
const finalStage = (newStage + Math.floor(returnTime)) % m;
const finalAtBase = [...newAtBase, returnPerson];
const finalAtDest = newAtDest.filter(x => x !== returnPerson);
const result = dfs(finalAtBase, finalAtDest, finalStage, totalTime + crossTime + returnTime);
minResult = Math.min(minResult, result);
}
}
}
}
memo.set(key, minResult);
return minResult;
}
const initialAtBase = Array.from({length: n}, (_, i) => i);
const result = dfs(initialAtBase, [], 0, 0);
return result === Infinity ? -1 : result;
};
复杂度分析
| 指标 | 复杂度 |
|---|---|
| 时间 | - |
| 空间 | - |