P7175: 开荒计划

---

【题目描述】

【问题描述】
小智总共选中了 n 块区域准备开垦田地，由于各块区域大小不一，开垦所需时间也不尽相同。据估算，其中第 i 块（1≤i≤n）区域的开垦耗时为 ti 天。这 n 块区域可以同时开垦，所以总耗时 tTotal 取决于耗时最长的区域，即：tTotal=max{t1,t2,⋯,tn}
为了加快开垦进度，小智准备在部分区域投入额外资源来缩短开垦时间。具体来说：
1、在第 i 块区域每投入 ci 单位资源，便可将其开垦耗时缩短 1 天；
2、耗时缩短天数以整数记，即第 i 块区域投入资源数量必须是 ci 的整数倍；
3、在第 i 块区域最多可投入 ci×(ti−k) 单位资源，将其开垦耗时缩短为 k 天；
4、这里的 k 表示开垦一块区域的最少天数，满足 0<k≤min{t1,t2,⋯,tn}；换言之，如果无限制地投入资源，所有区域都可以用 k 天完成开垦。
现在小智手中共有 m 单位资源可供使用，试计算开垦 n 块区域最少需要多少天？
【输入格式】
从标准输入读入数据。
输入共 n+1 行。
输入的第一行包含空格分隔的三个正整数 n、m 和 k，分别表示待开垦的区域总数、小智手上的资源数量和每块区域的最少开垦天数。
接下来 n 行，每行包含空格分隔的两个正整数 ti 和 ci，分别表示第 i 块区域开垦耗时和将耗时缩短 1 天所需资源数量。
【输出格式】
输出到标准输出。
输出一个整数，表示开垦 n 块区域的最少耗时。
【样例输入1】
4 9 2
6 1
5 1
6 2
7 1
【样例输出1】
5
【样例解释】
如下表所示，投入 5 单位资源即可将总耗时缩短至 5 天。此时顿顿手中还剩余 4 单位资源，但无论如何安排，也无法使总耗时进一步缩短。

i	基础耗时ti	缩减1天所需资源 ci	投入资源数量	实际耗时
1	6	1	1	5
2	5	1	0	5
3	6	2	2	5
4	7	1	2	5

【样例输入2】
4 30 2
6 1
5 1
6 2
7 1
【样例输出2】
2
【样例解释】
投入 20 单位资源，恰好可将所有区域开垦耗时均缩短为 k=2 天；受限于 k，剩余的 10 单位资源无法使耗时进一步缩短。
【子任务】
70% 的测试数据满足：0<n,ti,ci≤100 且 0<m≤1000000；
全部的测试数据满足：0<n,ti,ci≤100000 且 0<m≤1000000000。
 

题目类型~

2023集训营 

咻咻~

提交答案 状态 返回