2023-07-22：一共有n个项目，每个项目都有两个信息，

projects[i] = {a, b}，

表示i号项目做完要a天，但是当你投入b个资源，它就会缩短1天的时间，

你一共有k个资源，你的目标是完成所有的项目，但是希望总天数尽可能缩短。

在所有项目同时开工的情况下，返回尽可能少的天数。

1 <= n <= 10^5，

1 <= k <= 10^7。

答案2023-07-22：

以下是代码的大致过程和功能描述：

1.导入所需的包：fmt 用于打印输出，math 用于数学运算。

2.定义函数 minDays，该函数接受项目详情和可用资源数量作为输入参数。

3.初始化变量 l 和 r，用于跟踪搜索范围的左右边界。

4.遍历项目列表，并更新 r 的值为当前 r 和项目完成时间 (project[0]) 中的最大值。

5.将变量 m 和 ans 初始化为 r，作为找到的目标最少天数的初始猜测。

6.使用二分搜索算法找到最小天数。重复以下步骤，直到 l 小于等于 r：

• 计算中间值 m，即 l 和 r 的平均值。

• 如果在 m 天或更少的时间内完成所有项目所需的总资源量 (yeah(projects, m)) 小于等于可用资源量 k，则更新 ans 为 m，并将右边界 r 调整为 m - 1。

• 否则，将左边界 l 调整为 m + 1。

7.返回 ans 的最终值，表示完成所有项目所需的最少天数。

8.定义 yeah 函数，该函数接受项目详情和天数作为输入参数。

9.初始化变量 ans，用于跟踪所有需要的资源总量。

10.遍历项目列表，并计算超过给定天数的每个项目所需的资源量。

11.将每个项目所需的资源量添加到 ans。

12.返回 ans 的最终值，表示超过给定天数的所有项目所需的资源总量。

13.在 main 函数中，创建一个示例项目数据集 project，其中包含项目的详细信息。

14.将可用资源 k 设置为特定值。

15.打印调用 minDays 函数并传入项目数据集和可用资源作为参数的结果。

总的时间复杂度：

• minDays 函数中的二分搜索算法的时间复杂度为 O(log(r))，其中 r 是最大项目完成时间。

• yeah 函数中的遍历项目列表的时间复杂度为 O(n)，其中 n 是项目的数量。

因此，总的时间复杂度为 O(log(r) + n)。

总的空间复杂度：

• 空间复杂度主要来自于变量的存储和函数调用的堆栈空间。

• 不考虑输入数据的空间占用，变量和数据结构的空间复杂度是常数级的，不随输入规模的增长而变化。

• 函数调用的堆栈空间复杂度是 O(log(r) + n)，其中 r 是最大项目完成时间，n 是项目的数量。

因此，总的空间复杂度可以近似为 O(log(r) + n)。

go完整代码如下：

package main

import (
    "fmt"
    "math"
)

func minDays(projects [][]int, k int) int {
    l := 0
    r := 0
    for _, project := range projects {
        r = int(math.Max(float64(r), float64(project[0])))
    }
    m, ans := r, r
    for l <= r {
        m = (l + r) / 2
        if yeah(projects, m) <= k {
            ans = m
            r = m - 1
        } else {
            l = m + 1
        }
    }
    return ans
}

func yeah(projects [][]int, days int) int {
    ans := 0
    for _, p := range projects {
        if p[0] > days {
            ans += (p[0] - days) * p[1]
        }
    }
    return ans
}

func main() {
    project := [][]int{{1, 2}, {3, 4}, {5, 6}}
    k := 4
    fmt.Println(minDays(project, k))
}

rust完整代码如下：

fn main() {
    let project = vec![vec![1, 2], vec![3, 4], vec![5, 6]];
    let k = 4;
    println!("{}", min_days(&project, k));
}

fn min_days(projects: &Vec<Vec<i32>>, k: i32) -> i32 {
    let mut l = 0;
    let mut r = 0;
    for project in projects {
        r = r.max(project[0]);
    }
    let mut ans = r;
    while l <= r {
        let m = (l + r) / 2;
        if yeah(projects, m) <= k {
            ans = m;
            r = m - 1;
        } else {
            l = m + 1;
        }
    }
    ans
}

fn yeah(projects: &Vec<Vec<i32>>, days: i32) -> i32 {
    let mut ans = 0;
    for p in projects {
        if p[0] > days {
            ans += (p[0] - days) * p[1];
        }
    }
    ans
}

c++完整代码如下：

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

using namespace std;

int yeah(vector<vector<int>>& projects, int days);

int minDays(vector<vector<int>>& projects, int k) {
    int l = 0;
    int r = 0;

    for (auto project : projects) {
        r = max(r, project[0]);
    }

    int m, ans = r;

    while (l <= r) {
        m = (l + r) / 2;
        if (yeah(projects, m) <= k) {
            ans = m;
            r = m - 1;
        }
        else {
            l = m + 1;
        }
    }
    return ans;
}

int yeah(vector<vector<int>>& projects, int days) {
    int ans = 0;
    for (auto p : projects) {
        if (p[0] > days) {
            ans += (p[0] - days) * p[1];
        }
    }
    return ans;
}

int main() {
    vector<vector<int>> projects = { {1, 2}, {3, 4}, {5, 6} };
    int k = 4;

    int result = minDays(projects, k);

    cout << result << endl;

    return 0;
}

c完整代码如下：

#include <stdio.h>

int minDays(int projects[][2], int size, int k) {
    int l = 0;
    int r = 0;

    for (int i = 0; i < size; i++) {
        r = (projects[i][0] > r) ? projects[i][0] : r;
    }

    int m, ans = r;
    while (l <= r) {
        m = (l + r) / 2;
        if (yeah(projects, size, m) <= k) {
            ans = m;
            r = m - 1;
        }
        else {
            l = m + 1;
        }
    }
    return ans;
}

int yeah(int projects[][2], int size, int days) {
    int ans = 0;
    for (int i = 0; i < size; i++) {
        if (projects[i][0] > days) {
            ans += (projects[i][0] - days) * projects[i][1];
        }
    }
    return ans;
}

int main() {
    int projects[][2] = { {1, 2}, {3, 4}, {5, 6} };
    int size = sizeof(projects) / sizeof(projects[0]);
    int k = 4;

    int result = minDays(projects, size, k);
    printf("Result: %d\n", result);

    return 0;
}

本作品采用《CC 协议》，转载必须注明作者和本文链接