2023-07-22：一共有 n 个项目，每个项目都有两个信息， projects[i] = {a, b}，表示 i 号项目做完要 a 天，但是当你投入 b 个资源，它就会缩短 1 天的时间，你一共有 k 个资源，你的目

作者：福大大架构师每日一题

2023-07-22
北京
本文字数：2553 字
阅读完需：约 8 分钟

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;}