2026-03-23：完成所有送货任务的最少时间。用go语言，有两架送货无人机，对应两个长度为 2 的整数数组： - d = [d1, d2]：表示第 1 架和

福大大架构师每日一题

发布于 2026-03-31 21:18:45

220

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

2026-03-23：完成所有送货任务的最少时间。用go语言，有两架送货无人机，对应两个长度为 2 的整数数组：

• d = [d1, d2]：表示第 1 架和第 2 架无人机各自需要完成的送货次数
• r = [r1, r2]：表示第 1 架和第 2 架无人机的充电周期

规则如下：

• 每次送货固定耗时 1 小时
• 在同一时间内，最多只能有一架无人机执行送货任务
• 无人机 i 在时间为 ri 的倍数时必须进行充电，充电期间不能送货

目标是合理安排两架无人机的工作与充电时间，使得所有送货任务全部完成，并返回所需的最短总时间（单位：小时，整数）。

d = [d1, d2]。

1 <= di <= 1000000000。

r = [r1, r2]。

2 <= ri <= 3 * 10000。

输入: d = [3,1], r = [2,3]。

输出: 5。

解释:

第一架无人机在第 1、3、5 小时送货（在第 2、4 小时充电）。

第二架无人机在第 2 小时送货（在第 3 小时充电）。

题目来自力扣3733。

代码解题过程：

第一步：理解核心公式`f(d, r)`的含义

函数f(d, r) = d + (d-1)/(r-1)（整数除法）是单架无人机独立完成任务的最短时间。

• 单架无人机规则：每r小时必须充电1小时，每次送货1小时，同一时间只能干一件事；
• 公式含义：总时间 = 送货总耗时 + 充电总耗时；
• 举例验证：
1. 1. 第一架无人机：d1=3次，r1=2小时充电一次送货3次耗时3小时，充电次数=(3-1)/(2-1)=2次，总时间=3+2=5小时；
2. 2. 第二架无人机：d2=1次，r2=3小时充电一次送货1次耗时1小时，充电次数=(1-1)/(3-1)=0次，总时间=1+0=1小时。

第二步：计算两架无人机充电周期的最小公倍数`lcm(r1, r2)`

代码先算最大公约数gcd，再算最小公倍数lcm（两个数的公共充电周期）：

1. 计算gcd(2,3)：2和3的最大公约数是1；
2. 计算lcm(2,3)：2*3/1=6，即两架无人机每6小时会同时充电一次。

第三步：计算两架无人机合作完成总任务的最短时间

总送货次数 = d1+d2 = 3+1=4次，公共充电周期lcm=6；代入公式得合作时间：f(4,6) = 4 + (4-1)/(6-1) = 4+0=4（整数除法，3/5=0）。

第四步：取三个时间的最大值，得到最终答案

代码会计算三个关键时间，最大值就是满足所有规则的最少总时间：

1. 第一架无人机独立时间：5；
2. 第二架无人机独立时间：1；
3. 两架无人机合作总任务时间：4；
4. 最大值max(5,1,4)=5，与题目输出一致。

第五步：验证时间安排（匹配题目解释）

最终时间5小时，完美符合所有规则：

• 第1小时：无人机1送货；
• 第2小时：无人机2送货（无人机1充电）；
• 第3小时：无人机1送货（无人机2充电）；
• 第4小时：无人机1充电；
• 第5小时：无人机1送货； ✅ 完成3+1=4次送货，无时间冲突，无违规充电。

时间复杂度与额外空间复杂度分析

1. 时间复杂度

• 核心操作：gcd（欧几里得算法）、lcm、三次公式计算、取最大值；
• 欧几里得算法的时间复杂度为O(log(min(a,b)))，是对数级极小开销；
• 其余操作都是O(1) 常数时间；
• 总时间复杂度：O(log(min(r1, r2)))，可近似看作O(1)。

2. 额外空间复杂度

• 代码仅使用了固定数量的变量（d1,d2,r1,r2,lcm等），无数组、切片、动态内存分配；
• 额外空间不随输入数据规模变化；
• 总额外空间复杂度：O(1)。

总结

1. 解题核心：先算单架无人机独立时间，再算公共充电周期下的合作时间，最终取最大值；
2. 时间复杂度：O(log(min(r1,r2)))（近似常数级）；
3. 额外空间复杂度：O(1)（常数级）。

Go完整代码如下：

package main

import (
    "fmt"
)

func f(d, r int)int {
    return d + (d-1)/(r-1)
}

func minimumTime(d, r []int)int64 {
    d1, d2 := d[0], d[1]
    r1, r2 := r[0], r[1]
    l := lcm(r1, r2)
    returnint64(max(f(d1, r1), f(d2, r2), f(d1+d2, l)))
}

func gcd(a, b int)int {
    for a != 0 {
        a, b = b%a, a
    }
    return b
}

func lcm(a, b int)int {
    return a / gcd(a, b) * b
}

func main() {
    d := []int{3, 1}
    r := []int{2, 3}
    result := minimumTime(d, r)
    fmt.Println(result)
}

Python完整代码如下：

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

import math

def f(d: int, r: int) -> int:
    """计算单架无人机在给定充电周期下完成 d 次送货所需的最小小时数"""
    return d + (d - 1) // (r - 1)

def lcm(a: int, b: int) -> int:
    """计算最小公倍数"""
    return a // math.gcd(a, b) * b

def minimum_time(d: list, r: list) -> int:
    """
    计算两架无人机完成所有送货所需的最小总时间
    
    Args:
        d: 送货次数数组 [d1, d2]
        r: 充电周期数组 [r1, r2]
    
    Returns:
        最小总时间（小时数）
    """
    d1, d2 = d[0], d[1]
    r1, r2 = r[0], r[1]
    
    # 计算充电周期的最小公倍数
    l = lcm(r1, r2)
    
    # 取三种方案的最大值
    # 1. 第一架无人机单独完成所需时间
    # 2. 第二架无人机单独完成所需时间
    # 3. 两架无人机以 l 为周期协同工作完成所有任务所需时间
    return max(f(d1, r1), f(d2, r2), f(d1 + d2, l))

def main():
    d = [3, 1]
    r = [2, 3]
    result = minimum_time(d, r)
    print(result)

if __name__ == "__main__":
    main()

C++完整代码如下：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int f(int d, int r) {
    // 计算单架无人机在给定充电周期下完成 d 次送货所需的最小小时数
    return d + (d - 1) / (r - 1);
}

int gcd(int a, int b) {
    // 计算最大公约数
    while (a != 0) {
        int temp = a;
        a = b % a;
        b = temp;
    }
    return b;
}

int lcm(int a, int b) {
    // 计算最小公倍数
    return a / gcd(a, b) * b;
}

long long minimumTime(vector<int>& d, vector<int>& r) {
    int d1 = d[0], d2 = d[1];
    int r1 = r[0], r2 = r[1];

    // 计算充电周期的最小公倍数
    int l = lcm(r1, r2);

    // 取三种方案的最大值
    // 1. 第一架无人机单独完成所需时间
    // 2. 第二架无人机单独完成所需时间
    // 3. 两架无人机以 l 为周期协同工作完成所有任务所需时间
    return max({f(d1, r1), f(d2, r2), f(d1 + d2, l)});
}

int main() {
    vector<int> d = {3, 1};
    vector<int> r = {2, 3};

    long long result = minimumTime(d, r);
    cout << result << endl;

    return0;
}