顿顿总共选中了 n 块区域准备开垦田地,由于各块区域大小不一,开垦所需时间也不尽相同。
据估算,其中第 i 块(1≤i≤n)区域的开垦耗时为 ti 天。
这 n块区域可以同时开垦,所以总耗时 tTotal 取决于耗时最长的区域,即:tTotal=max{t1,t2,…,tn}
为了加快开垦进度,顿顿准备在部分区域投入额外资源来缩短开垦时间。
具体来说:
- 在第 i块区域每投入 ci 单位资源,便可将其开垦耗时缩短 1 天;
- 耗时缩短天数以整数记,即第 i 块区域投入资源数量必须是 ci 的整数倍;
- 在第 i块区域最多可投入 ci×(ti−k) 单位资源,将其开垦耗时缩短为 k�天;
- 这里的 k表示开垦一块区域的最少天数,满足 0<k≤min{t1,t2,…,tn};换言之,如果无限制地投入资源,所有区域都可以用 k天完成开垦。
现在顿顿手中共有 m单位资源可供使用,试计算开垦 n 块区域最少需要多少天?