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;
}
标签:22,项目,int,days,project,一共,ans,projects
From: https://www.cnblogs.com/moonfdd/p/17574224.html