【CSP】202303-2_垦田计划Python实现
试题编号
试题名称
时间限制
内存限制
问题描述
- 顿顿总共选中了 n n n块区域准备开垦田地,由于各块区域大小不一,开垦所需时间也不尽相同。据估算,其中第 i i i块 ( 1 ≤ i ≤ n ) (1 \leq i \leq n) (1≤i≤n)区域的开垦耗时为 t i t_{i} ti?天,这 n n n块区域可以同时开垦,所以总耗时 t T o t a l t_{Total} tTotal?取决于耗时最长的区域,即:
t T o t a l = max ? { ? t 1 , t 2 , ? ? , t n ? } t_{Total} = \max\set{t_{1} , t_{2} , \cdots , t_{n}} tTotal?=max{t1?,t2?,?,tn?}
- 为了加快开垦进度,顿顿准备在部分区域投入额外资源来缩短开垦时间,具体来说:
- 在第 i i i块区域每投入 c i c_{i} ci?单位资源,便可将其开垦耗时缩短 1 1 1天
- 耗时缩短天数以整数记,即第 i i i块区域投入资源数量必须是 c i c_{i} ci?的整数倍
- 在第 i i i块区域最多可投入 c i × ( t i ? k ) c_{i} \times (t_{i} - k) ci?×(ti??k)单位资源,将其开垦耗时缩短为 k k k天
- 这里的 k k k表示开垦一块区域的最少天数,满足 0 < k ≤ min ? { ? t 1 , t 2 , ? ? , t n ? } 0 < k \leq \min\set{t_{1} , t_{2} , \cdots ,t_{n}} 0<k≤min{t1?,t2?,?,tn?};换言之,如果无限制地投入资源,所有区域都可以用 k k k天完成开垦
- 现在顿顿手中共有 m m m单位资源可供使用,试计算开垦 n n n块区域最少需要多少天
输入格式
- 从标准输入读入数据
- 输入共 n + 1 n + 1 n+1行
- 输入的第一行包含空格分隔的三个正整数 n n n、 m m m和 k k k,分别表示待开垦的区域总数、顿顿手上的资源数量和每块区域的最少开垦天数
- 接下来 n n n行,每行包含空格分隔的两个正整数 t i t_{i} ti?和 c i c_{i} ci?,分别表示第 i i i块区域开垦耗时和将耗时缩短 1 1 1天所需资源数量
输出格式
- 输出到标准输出
- 输出一个整数,表示开垦 n n n块区域的最少耗时
样例输入1
4 9 2
6 1
5 1
6 2
7 1
样例输出1
5
样例解释
- 如下表所示,投入 5 5 5单位资源即可将总耗时缩短至 5 5 5天,此时顿顿手中还剩余 4 4 4单位资源,但无论如何安排,也无法使总耗时进一步缩短
i i i | 基础耗时 | t i t_{i} ti?缩减 1 1 1天所需资源 | c i c_{i} ci?投入资源数量 | 实际耗时 |
---|---|---|---|---|
1 1 1 | 6 6 6 | 1 1 1 | 1 1 1 | 5 5 5 |
2 2 2 | 5 5 5 | 1 1 1 | 0 0 0 | 5 5 5 |
3 3 3 | 6 6 6 | 2 2 2 | 2 2 2 | 5 5 5 |
4 4 4 | 7 7 7 | 1 1 1 | 2 2 2 | 5 5 5 |
样例输入2
4 30 2
6 1
5 1
6 2
7 1
样例输出2
2
样例解释
- 投入 20 20 20单位资源,恰好可将所有区域开垦耗时均缩短为 k = 2 k = 2 k=2天;受限于 k k k,剩余的 10 10 10单位资源无法使耗时进一步缩短
子任务
- 70 % 70\% 70%的测试数据满足: 0 < n 0 < n 0<n, t i t_{i} ti?, c i ≤ 100 c_{i} \leq 100 ci?≤100且 0 < m ≤ 1 0 6 0 < m \leq 10^{6} 0<m≤106
- 全部的测试数据满足: 0 < n 0 < n 0<n, t i t_{i} ti?, c i ≤ 1 0 5 c_{i} \leq 10^{5} ci?≤105且 0 < m ≤ 1 0 9 0 < m \leq 10^{9} 0<m≤109
Python
实现
n, m, k = map(int, input().split())
days = []
for _ in range(n):
days.append(list(map(int, input().split())))
def judge(x):
sum = 0
for i in range(n):
if days[i][0] < x:
continue
sum += (days[i][0] - x) * days[i][1]
if sum <= m:
return True
else:
return False
l, r = k, max(days, key=lambda x: x[0])[0]
while l <= r:
mid = (l + r) // 2
if judge(mid):
r = mid - 1
else:
l = mid + 1
print(l)
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!