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;
} 在這裡插入圖檔描述
福大大架構師每日一題java當死，golang當立。最新面試題，涉及golang，rust，mysql，redis，雲原生，算法，分布式，網絡，作業系統。
公衆号