2023-07-22：一共有n個(gè)項(xiàng)目，每個(gè)項(xiàng)目都有兩個(gè)信息， projects[i] = {a, b}， 表示i號
2023-07-22：一共有n個(gè)項(xiàng)目，每個(gè)項(xiàng)目都有兩個(gè)信息，
projects[i] = {a, b}，
表示i號項(xiàng)目做完要a天，但是當(dāng)你投入b個(gè)資源，它就會縮短1天的時(shí)間，
你一共有k個(gè)資源，你的目標(biāo)是完成所有的項(xiàng)目，但是希望總天數(shù)盡可能縮短。
在所有項(xiàng)目同時(shí)開工的情況下，返回盡可能少的天數(shù)。
1 <= n <= 10^5，
1 <= k <= 10^7。
答案2023-07-22：
以下是代碼的大致過程和功能描述：
1.導(dǎo)入所需的包：fmt?用于打印輸出，math?用于數(shù)學(xué)運(yùn)算。
2.定義函數(shù)?minDays，該函數(shù)接受項(xiàng)目詳情和可用資源數(shù)量作為輸入?yún)?shù)。
3.初始化變量?l?和?r，用于跟蹤搜索范圍的左右邊界。
4.遍歷項(xiàng)目列表，并更新?r?的值為當(dāng)前?r?和項(xiàng)目完成時(shí)間 (project[0]) 中的最大值。
5.將變量?m?和?ans?初始化為?r，作為找到的目標(biāo)最少天數(shù)的初始猜測。
6.使用二分搜索算法找到最小天數(shù)。重復(fù)以下步驟，直到?l?小于等于?r：
??計(jì)算中間值?
m，即?l?和?r?的平均值。??如果在?
m?天或更少的時(shí)間內(nèi)完成所有項(xiàng)目所需的總資源量 (yeah(projects, m)) 小于等于可用資源量?k，則更新?ans?為?m，并將右邊界?r?調(diào)整為?m - 1。??否則，將左邊界?
l?調(diào)整為?m + 1。
7.返回?ans?的最終值，表示完成所有項(xiàng)目所需的最少天數(shù)。
8.定義?yeah?函數(shù)，該函數(shù)接受項(xiàng)目詳情和天數(shù)作為輸入?yún)?shù)。
9.初始化變量?ans，用于跟蹤所有需要的資源總量。
10.遍歷項(xiàng)目列表，并計(jì)算超過給定天數(shù)的每個(gè)項(xiàng)目所需的資源量。
11.將每個(gè)項(xiàng)目所需的資源量添加到?ans。
12.返回?ans?的最終值，表示超過給定天數(shù)的所有項(xiàng)目所需的資源總量。
13.在?main?函數(shù)中，創(chuàng)建一個(gè)示例項(xiàng)目數(shù)據(jù)集?project，其中包含項(xiàng)目的詳細(xì)信息。
14.將可用資源?k?設(shè)置為特定值。
15.打印調(diào)用?minDays?函數(shù)并傳入項(xiàng)目數(shù)據(jù)集和可用資源作為參數(shù)的結(jié)果。
總的時(shí)間復(fù)雜度：
??
minDays?函數(shù)中的二分搜索算法的時(shí)間復(fù)雜度為 O(log(r))，其中 r 是最大項(xiàng)目完成時(shí)間。??
yeah?函數(shù)中的遍歷項(xiàng)目列表的時(shí)間復(fù)雜度為 O(n)，其中 n 是項(xiàng)目的數(shù)量。
因此，總的時(shí)間復(fù)雜度為 O(log(r) + n)。
總的空間復(fù)雜度：
??空間復(fù)雜度主要來自于變量的存儲和函數(shù)調(diào)用的堆?？臻g。
??不考慮輸入數(shù)據(jù)的空間占用，變量和數(shù)據(jù)結(jié)構(gòu)的空間復(fù)雜度是常數(shù)級的，不隨輸入規(guī)模的增長而變化。
??函數(shù)調(diào)用的堆棧空間復(fù)雜度是 O(log(r) + n)，其中 r 是最大項(xiàng)目完成時(shí)間，n 是項(xiàng)目的數(shù)量。
因此，總的空間復(fù)雜度可以近似為 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++完整代碼如下：
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完整代碼如下：
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;
}
