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

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助力您的未来发展。