网易首页 > 网易号 > 正文 申请入驻

2026-10-30:最小化最大可能等待时间。用go语言,有一个整数数组 demand,其中 demand[i] 表示第 i 辆车完成加油所需的燃料量。另有长度

0
分享至

2026-10-30:最小化最大可能等待时间。用go语言,有一个整数数组 dem)and,其中 demand[i] 表示第 i 辆车完成加油所需的燃料量。另有长度为 2 的数组 fuel,fuel[0] 和 fuel[1] 分别表示两个供油设备的初始可用燃料量。

车辆必须按下标从小到大处理。第 0 辆车在时刻 0 获得开始资格;对于 i > 0,第 i 辆车会在第 i-1 辆车真正开始加油的那一刻获得开始资格。

每个供油设备同一时间只能服务一辆车。车辆只能选择一台当前空闲、并且剩余燃料不少于 demand[i] 的设备开始加油。车辆一旦选定设备,就不能改选,也不能在该设备空闲后故意继续等待;如果选定时设备忙,它要等到该设备空闲后立刻开始。为车辆供油需要 demand[i] 秒,开始后不能中断,并会从所选设备的剩余燃料中扣除 demand[i]。

当两台设备都空闲,且它们的剩余燃料都不足以满足当前待处理车辆的需求时,整个流程结束,后面的车辆都无法再被服务。

某辆车的等待时间,是从它获得开始资格到它真正开始加油之间的时间。

目标是:先让被服务的车辆数量尽可能多;在所有能达到这个最大服务数量的方案中,再让所有被服务车辆中的最大等待时间尽可能小。返回这个最小可能的最大等待时间。如果任何车辆都无法被服务,返回 -1。

1 <= demand.length <= 50。

1 <= demand[i] <= 20。

fuel.length == 2。

1 <= fuel[i] <= 50。

输入: demand = [6,8,4,6,5], fuel = [16,13]。

输出: 6。

解释:

车辆

被允许的时间

开始加油的时间

使用的加油机

开始前的剩余燃料(加油机 0,加油机 1)

等待时间

0

0

0

0

(16, 13)

0

1

0

0

1

(10, 13)

0

2

0

6

0

(10, 5)

6

3

6

10

0

(6, 5)

4

4

10

10

1

(0, 5)

0

因此,所有 5 辆车都得到了服务,最大等待时间为 6。

为了服务所有 5 辆车,加油机 0 必须服务 demand 为 6、4 和 6 的车辆,而加油机 1 必须服务 demand 为 8 和 5 的车辆。因此,车辆 2 必须等到时间 6 才能让加油机 0 空闲,所以任何服务所有 5 辆车的分配方案,其最大等待时间都不可能小于 6。

题目来自力扣4009。

大体步骤如下: 一、第一阶段:求最多能服务多少辆车

函数calcMaxCars负责计算从第i辆车开始,在两台设备剩余燃料分别为fuel0、fuel1时,最多还能服务多少辆车。

1. 状态定义

状态为:

  • •i:当前处理到第几辆车;

  • •fuel0:第 0 台供油设备当前剩余燃料;

  • •fuel1:第 1 台供油设备当前剩余燃料。

递归函数返回:在该状态下,最多还能服务的车辆数量。

2. 递归转移

对于第i辆车,需求量为demand[i]。

  • • 如果第 0 台设备剩余燃料足够,即demand[i] <= fuel0,则可以让第i辆车使用第 0 台设备,之后设备 0 剩余燃料减少demand[i],服务车辆数加 1。

  • • 如果第 1 台设备剩余燃料足够,即demand[i] <= fuel1,则可以让第i辆车使用第 1 台设备,之后设备 1 剩余燃料减少demand[i],服务车辆数加 1。

  • • 两种选择取能服务车辆数的较大值。

如果两台设备剩余燃料都不足以服务当前车辆,则从当前车辆开始一辆也无法服务,返回 0。

这里没有“跳过当前车辆继续服务后面车辆”的分支,因为车辆必须按顺序处理;一旦当前车辆无法被任何设备服务,整个流程就结束,后面的车辆也无法被服务。

3. 记忆化

使用一个以(i, fuel0, fuel1)为键的记忆表,避免同一状态重复计算。这样最多考虑:

  • •i有n + 1种;

  • •fuel0不超过初始fuel[0];

  • •fuel1不超过初始fuel[1]。

得到全局最大服务车辆数maxCars。

如果maxCars == 0,说明任何车辆都无法服务,直接返回-1。

二、第二阶段:二分最小最大等待时间

记候选的“最大等待时间”为W。

1. 为什么可以二分

如果存在一种方案,使所有被服务车辆的等待时间都不超过W,那么对于更大的W' > W,同一方案也满足等待时间不超过W'。因此可行性关于W单调。

所以在范围[0, max(demand))中二分,寻找最小的可行W。如果搜索范围内都不可行,则返回上界max(demand)。

2. 检查函数check(W)

check(W)判断:在每辆车等待时间都不超过W的约束下,能否服务前maxCars辆车。

因为第一阶段已经确定最多能服务maxCars辆,而服务顺序必须从前往后,所以只需检查前maxCars辆车是否都能被安排服务。

三、check(W)中的深度优先搜索

检查函数内部使用 DFS,状态为:

(i, wait1, fuel0, fuel1)

含义如下:

  • •i:当前要安排第i辆车;

  • •fuel0:上一辆车所用设备的剩余燃料;

  • •fuel1:另一台设备的剩余燃料;

  • •wait1:如果当前第i辆车改选“另一台设备”,它需要等待的时间。

同时令:

wait0 = demand[i-1](当i > 0时),否则wait0 = 0。

wait0的含义是:如果当前第i辆车继续使用“上一辆车所用的同一台设备”,那么它需要等待的时间。因为第i辆车获得开始资格的时刻,正好是第i-1辆车真正开始加油的时刻,而第i-1辆车需要占用该设备demand[i-1]时间,所以等待时间就是demand[i-1]。

DFS 中尝试两种选择:

选择 1:当前车辆继续使用上一辆车所用的设备

需要同时满足:

  • •wait0 <= W,即等待时间不超过当前最大等待时间限制;

  • •demand[i] <= fuel0,即该设备剩余燃料足够。

如果选择该设备,则:

  • • 当前车辆等待时间为wait0;

  • • 该设备剩余燃料变为fuel0 - demand[i];

  • • 经过wait0时间后,另一台设备原本的等待时间wait1会减少wait0,变为max(wait1 - wait0, 0);

  • • 下一辆车继续以当前车辆所用设备作为“上一辆车所用设备”,因此设备角色不交换。

然后递归处理第i+1辆车。

选择 2:当前车辆改选另一台设备

需要同时满足:

  • •wait1 <= W,即当前车辆等待另一台设备空闲的时间不超过限制;

  • •demand[i] <= fuel1,即另一台设备剩余燃料足够。

如果选择另一台设备,则:

  • • 当前车辆等待时间为wait1;

  • • 该设备剩余燃料变为fuel1 - demand[i];

  • • 经过wait1时间后,原来“上一辆车所用设备”的等待时间会变为max(wait0 - wait1, 0);

  • • 因为当前车辆改用了另一台设备,所以对下一辆车来说,“上一辆车所用设备”变成了原来的另一台设备。因此递归时两台设备的角色要交换:新的fuel0是fuel1 - demand[i],新的fuel1是原来的fuel0,新的wait1是max(wait0 - wait1, 0)。

然后递归处理第i+1辆车。

终止条件

  • • 如果i == maxCars,说明前maxCars辆车都安排成功,返回可行。

  • • 如果两种选择都无法满足等待时间或燃料约束,则当前分支失败。

去重剪枝

使用一个访问集合记录已经搜索过的状态(i, wait1, fuel0, fuel1)。如果同一状态之前已经访问过且没有成功,则再次遇到时直接返回失败,避免重复搜索。

由于递归中i每次递增,不会形成环,因此这种访问标记是安全的。

四、返回结果

二分结束后,返回最小的可行最大等待时间。若第一阶段发现最多服务 0 辆,则返回-1。

五、复杂度分析

设:

  • •n = demand.length;

  • •D = max(demand);

  • •F0 = fuel[0];

  • •F1 = fuel[1]。

1. 第一阶段calcMaxCars

状态数为:

O(n * F0 * F1)

每个状态做常数次转移,因此时间复杂度为:

O(n * F0 * F1)

记忆表占用空间:

O(n * F0 * F1)

2. 第二阶段每次check(W)

DFS 状态为(i, wait1, fuel0, fuel1):

  • •i最多maxCars <= n;

  • •wait1由等待时间差产生,范围不超过D;

  • • 两台设备的剩余燃料组合最多为O(F0 * F1)的常数倍,因为设备角色可能交换,但仍是常数倍。

所以每次检查的状态数为:

O(n * D * F0 * F1)

每轮check的时间复杂度为:

O(n * D * F0 * F1)

访问集合vis占用空间:

O(n * D * F0 * F1)

二分次数为:

O(log D)

因此第二阶段总时间复杂度为:

O(log D * n * D * F0 * F1)

3. 总时间复杂度

总时间复杂度为:

O(n * F0 * F1 + log D * n * D * F0 * F1)

即:

O(n * F0 * F1 * (1 + D * log D))

若令F = max(F0, F1),也可写成:

O(n * F^2 + log D * n * D * F^2)

4. 总额外空间复杂度

需要同时考虑:

  • • 第一阶段记忆表:O(n * F0 * F1);

  • • 第二阶段单次check的访问集合:O(n * D * F0 * F1);

  • • 递归栈深度最多O(n)。

因此总额外空间复杂度为:

O(n * D * F0 * F1)

若令F = max(F0, F1),则为:

O(n * D * F^2)

在题目约束下,n <= 50,D <= 20,fuel[i] <= 50,状态规模是可控的。

Go完整代码如下:

package main

import (
"fmt"
"slices"
"sort"
)

func minMaxWaitingTime(demand []int, fuel []int)int {
// 1. 求出最多能服务的车辆数 maxCars
type fuelArgs struct{ i, fuel0, fuel1 int }
memo := map[fuelArgs]int{}

var calcMaxCars func(int, int, int)int
calcMaxCars = func(i, fuel0, fuel1 int) (res int) {
if i == len(demand) {
return0
}

args := fuelArgs{i, fuel0, fuel1}
if v, ok := memo[args]; ok {
return v
}

d := demand[i]
if d <= fuel0 {
res = calcMaxCars(i+1, fuel0-d, fuel1) + 1
}
if d <= fuel1 {
res = max(res, calcMaxCars(i+1, fuel0, fuel1-d)+1)
}

memo[args] = res
return
}

maxCars := calcMaxCars(0, fuel[0], fuel[1])
if maxCars == 0 {
return-1
}

// 2. 二分最大等待时间
ans := sort.Search(slices.Max(demand), func(maxWaitingTime int)bool {
// 3. 判断在最大等待时间 <= maxWaitingTime 的约束下,能否服务 maxCars 辆车
type state struct{ i, wait1, fuel0, fuel1 int }
vis := map[state]bool{}

var dfs func(int, int, int, int)bool
dfs = func(i, wait1, fuel0, fuel1 int)bool {
if i == maxCars {
returntrue
}

st := state{i, wait1, fuel0, fuel1}
if vis[st] {
returnfalse
}
vis[st] = true

wait0 := 0
if i > 0 {
wait0 = demand[i-1]
}
d := demand[i]

// 跟在车 i-1 后面加油
if wait0 <= maxWaitingTime && d <= fuel0 &&
dfs(i+1, max(wait1-wait0, 0), fuel0-d, fuel1) {
returntrue
}

// 不跟在车 i-1 后面加油
if wait1 <= maxWaitingTime && d <= fuel1 &&
dfs(i+1, max(wait0-wait1, 0), fuel1-d, fuel0) { // 注意这里交换了 fuel0 和 fuel1
returntrue
}

returnfalse
}

return dfs(0, 0, fuel[0], fuel[1])
})
return ans
}

func main() {
demand := []int{6, 8, 4, 6, 5}
fuel := []int{16, 13}
result := minMaxWaitingTime(demand, fuel)
fmt.Println(result)
}

Python完整代码如下:

# -*-coding:utf-8-*-

import sys

# 增加递归深度限制,防止深递归导致 RecursionError
sys.setrecursionlimit(1000000)

def minMaxWaitingTime(demand, fuel):
n = len(demand)

# 1. 求出最多能服务的车辆数 maxCars
memo = {}

def calcMaxCars(i, fuel0, fuel1):
if i == n:
return0

key = (i, fuel0, fuel1)
if key in memo:
return memo[key]

d = demand[i]
res = 0
if d <= fuel0:
res = max(res, calcMaxCars(i + 1, fuel0 - d, fuel1) + 1)
if d <= fuel1:
res = max(res, calcMaxCars(i + 1, fuel0, fuel1 - d) + 1)

memo[key] = res
return res

maxCars = calcMaxCars(0, fuel[0], fuel[1])
if maxCars == 0:
return-1

# 2. 判断在最大等待时间 <= maxWaitingTime 的约束下,能否服务 maxCars 辆车
def check(maxWaitingTime):
vis = set()

def dfs(i, wait1, fuel0, fuel1):
if i == maxCars:
return True

st = (i, wait1, fuel0, fuel1)
if st in vis:
return False
vis.add(st)

wait0 = 0if i == 0else demand[i - 1]
d = demand[i]

# 跟在车 i-1 后面加油
if wait0 <= maxWaitingTime and d <= fuel0:
if dfs(i + 1, max(wait1 - wait0, 0), fuel0 - d, fuel1):
return True

# 不跟在车 i-1 后面加油
if wait1 <= maxWaitingTime and d <= fuel1:
if dfs(i + 1, max(wait0 - wait1, 0), fuel1 - d, fuel0):
return True

return False

return dfs(0, 0, fuel[0], fuel[1])

# 3. 二分最大等待时间
lo, hi = 0, max(demand)
while lo < hi:
mid = (lo + hi) // 2
if check(mid):
hi = mid
else:
lo = mid + 1
return lo

def main():
demand = [6, 8, 4, 6, 5]
fuel = [16, 13]
result = minMaxWaitingTime(demand, fuel)
print(result)

if __name__ == "__main__":
main()
C++完整代码如下:

  

using namespace std;

int minMaxWaitingTime(vector& demand, vector& fuel) {
int n = demand.size();

// 1. 求出最多能服务的车辆数 maxCars
map int , int , int >, int > memo;

function< int ( int , int , int )> calcMaxCars = [&]( int i, int fuel0, int fuel1) -> int {
if (i == n) return 0 ;

auto key = make_tuple(i, fuel0, fuel1);
auto it = memo.find(key);
if (it != memo.end()) return it->second;

int d = demand[i];
int res = 0 ;
if (d <= fuel0) res = calcMaxCars(i + 1 , fuel0 - d, fuel1) + 1 ;
if (d <= fuel1) res = max(res, calcMaxCars(i + 1 , fuel0, fuel1 - d) + 1 );

memo[key] = res;
return res;
};

int maxCars = calcMaxCars( 0 , fuel[ 0 ], fuel[ 1 ]);
if (maxCars == 0 ) return -1 ;

// 2/3. 判断在最大等待时间 <= maxWaitingTime 的约束下,能否服务 maxCars 辆车
auto check = [&]( int maxWaitingTime) -> bool {
map int , int , int , int >, bool > vis;

function< bool ( int , int , int , int )> dfs = [&]( int i, int wait1, int fuel0, int fuel1) -> bool {
if (i == maxCars) return true ;

auto st = make_tuple(i, wait1, fuel0, fuel1);
if (vis.count(st)) return false ;
vis[st] = true ;

int wait0 = (i == 0 ) ? 0 : demand[i - 1 ];
int d = demand[i];

// 跟在车 i-1 后面加油
if (wait0 <= maxWaitingTime && d <= fuel0 &&
dfs(i + 1 , max(wait1 - wait0, 0 ), fuel0 - d, fuel1))
return true ;

// 不跟在车 i-1 后面加油(交换两辆车)
if (wait1 <= maxWaitingTime && d <= fuel1 &&
dfs(i + 1 , max(wait0 - wait1, 0 ), fuel1 - d, fuel0))
return true ;

return false ;
};

return dfs( 0 , 0 , fuel[ 0 ], fuel[ 1 ]);
};

// 模拟 Go 中 sort.Search 语义:在 [0, max(demand)) 中找最小的 i 使 check(i) 为真,
// 若均不满足则返回 max(demand)
int hi = *max_element(demand.begin(), demand.end());
int lo = 0 ;
while (lo < hi) {
int mid = lo + (hi - lo) / 2 ;
if (check(mid)) hi = mid;
else lo = mid + 1 ;
}
return lo;
}

int main() {
vector< int > demand = { 6 , 8 , 4 , 6 , 5 };
vector< int > fuel = { 16 , 13 };
cout << minMaxWaitingTime(demand, fuel) << endl;
return 0 ;
}

我们相信人工智能为普通人提供了一种“增强工具”,并致力于分享全方位的AI知识。在这里,您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”,发消息可获得面试资料,让AI助力您的未来发展。

特别声明:以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布,本平台仅提供信息存储服务。

Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.

相关推荐
热点推荐
还有谁?央视最高规格致敬C罗,一整期节目全是他,催泪告白:有一种英雄主义叫C罗

还有谁?央视最高规格致敬C罗,一整期节目全是他,催泪告白:有一种英雄主义叫C罗

球盲百小易
2026-11-17 00:59:04
人民日报推荐的双腿提踵!不起眼的踮脚,好处远超你的想象

人民日报推荐的双腿提踵!不起眼的踮脚,好处远超你的想象

解说阿洎
2026-10-19 04:57:50
官宣了!罗伯特・帕丁森成为新一任007

官宣了!罗伯特・帕丁森成为新一任007

齐鲁壹点
2026-11-17 07:20:15
比缅北凶险100倍!曾经的旅游胜地,如今黄赌毒俱全,乱象随处可见

比缅北凶险100倍!曾经的旅游胜地,如今黄赌毒俱全,乱象随处可见

琅琊财经
2026-07-31 22:02:18
广州豹官方发布投票:选出您心仪的广州豹2027赛季主场

广州豹官方发布投票:选出您心仪的广州豹2027赛季主场

懂球帝
2026-11-17 19:39:11
大二女生去按摩,男技师让她脱内裤跪着背对着他,整个人贴了上来,店长:包厢没监控,赔700块

大二女生去按摩,男技师让她脱内裤跪着背对着他,整个人贴了上来,店长:包厢没监控,赔700块

一丝不苟的法律人
2026-11-08 16:44:48
中国首富张一鸣建议公司员工,不要住在城乡结合部,应该全部住在北京市区,哪怕房子小点,省下的时间可以健身读书看电影!

中国首富张一鸣建议公司员工,不要住在城乡结合部,应该全部住在北京市区,哪怕房子小点,省下的时间可以健身读书看电影!

财经要参
2026-11-09 12:00:05
这身材这颜值就是带个儿子也有大把男人要啊

这身材这颜值就是带个儿子也有大把男人要啊

草莓解说体育
2026-11-18 08:03:09
高三男孩喀纳斯湖失踪,母亲守岸7天后直言放弃,意外竟在此时发生

高三男孩喀纳斯湖失踪,母亲守岸7天后直言放弃,意外竟在此时发生

古怪奇谈录
2025-10-16 10:53:42
男子为滋补,生吞新鲜蛇胆,大约花生米大小!3个月后抽搐倒地,检查结果让人吓一跳:脑子里长满寄生虫;医生:生蛇胆不是补品

男子为滋补,生吞新鲜蛇胆,大约花生米大小!3个月后抽搐倒地,检查结果让人吓一跳:脑子里长满寄生虫;医生:生蛇胆不是补品

科学大观园
2026-11-17 08:02:56
教育厅长的愧疚、学校的秋假商请函,谁在偷走孩子的时间

教育厅长的愧疚、学校的秋假商请函,谁在偷走孩子的时间

行者殷涛
2026-11-17 14:54:53
被嘲讽电梯战神!37岁王刚笑了:一开始很抵触 后觉得这是球迷的爱

被嘲讽电梯战神!37岁王刚笑了:一开始很抵触 后觉得这是球迷的爱

风过乡
2026-11-17 08:57:51
1947年,汉奸丁默邨临刑前的最后一搏:他要和蒋介石做一笔特殊的交易

1947年,汉奸丁默邨临刑前的最后一搏:他要和蒋介石做一笔特殊的交易

唠叨说历史
2026-11-17 16:18:34
房地产一旦撑不住,明年国内房价或许会碰到三个大难题 卖房救急的人,得先借钱救急

房地产一旦撑不住,明年国内房价或许会碰到三个大难题 卖房救急的人,得先借钱救急

新国学文化
2026-11-17 11:36:37
主将缺席!新狼王崛起!34分队史第一!狼队有机会吗?

主将缺席!新狼王崛起!34分队史第一!狼队有机会吗?

篮球盛世
2026-11-17 13:03:08
砒霜口服药让一类白血病患者存活率超97%,康复患者发声:药物的味道像海水一样,如果我不告诉别人,他们不可能知道我在一年多前曾患血癌

砒霜口服药让一类白血病患者存活率超97%,康复患者发声:药物的味道像海水一样,如果我不告诉别人,他们不可能知道我在一年多前曾患血癌

大风新闻
2026-11-16 10:40:08
江苏,女子在菜场借给陌生男子10元救急,十年后在公交偶遇让其还钱,男子反将女子殴打致骨折:“都怪你!”法院判决亮了

江苏,女子在菜场借给陌生男子10元救急,十年后在公交偶遇让其还钱,男子反将女子殴打致骨折:“都怪你!”法院判决亮了

励职派
2026-11-17 13:05:31
网友背着30斤重的柯基与背着40斤重的萨摩耶主人在山上相遇,狗主人对视而笑,两狗难分伯仲…评论区:还有只拉布拉多更是重量级…

网友背着30斤重的柯基与背着40斤重的萨摩耶主人在山上相遇,狗主人对视而笑,两狗难分伯仲…评论区:还有只拉布拉多更是重量级…

大爱狗狗控
2026-11-12 20:46:25
直播打赏的钱怎么分成,刷个3000块的嘉年华主播到底能拿多少?

直播打赏的钱怎么分成,刷个3000块的嘉年华主播到底能拿多少?

草莓解说体育
2026-11-18 02:13:15
贵州2026:全国第21,超山西!工业猛,收入增,贵阳崛起,安顺差

贵州2026:全国第21,超山西!工业猛,收入增,贵阳崛起,安顺差

奇思妙想生活家
2026-11-18 08:23:57
2026-11-18 09:43:00
moonfdd incentive-icons
moonfdd
福大大架构师每日一题
1582文章数 83关注度
往期回顾 全部

科技要闻

老黄想回来?英伟达董事会:没门

头条要闻

中国女子在希腊失踪半年 保险箱发现10万欧元现金

头条要闻

中国女子在希腊失踪半年 保险箱发现10万欧元现金

体育要闻

伪强队?拥4亿豪阵欧国联6连败+世界杯出局

娱乐要闻

陈晓楠对话厉娜和许飞引全网热议

财经要闻

10万人逼宫英伟达,黄仁勋要复职了?

汽车要闻

更豪华更好开 问界新M8细节升级见真章

态度原创

教育
家居
健康
时尚
军事航空

教育要闻

济南市历下区燕山小学教育集团将出席2026第四届课博会,解码“做中学”视域下小学科学教育生态构建

家居要闻

2026建博会(广州) 公装联探展交流活动

情绪真能让健康人"伤心至死"?

秋天衣服别总穿纯色,试试这几件条纹单品,简单时尚又减龄

军事要闻

美军在中东再成三航母之势

无障碍浏览 进入关怀版