当前位置：首页 > news >正文

【CSP】202303-2_垦田计划Python实现

news 来源：原创 2024/5/12 0:14:48

文章目录

@[toc]
试题编号
试题名称
时间限制
内存限制
问题描述
输入格式
输出格式
样例输入1
样例输出1
样例解释
样例输入2
样例输出2
样例解释
子任务
`Python`实现

试题编号

202303-2

试题名称

垦田计划

时间限制

1.0s

内存限制

512.0MB

问题描述

顿顿总共选中了 $n$ 块区域准备开垦田地，由于各块区域大小不一，开垦所需时间也不尽相同。据估算，其中第 $i$ 块 $\leq i \leq n)$ 区域的开垦耗时为 $t_{i}$ 天，这 $n$ 块区域可以同时开垦，所以总耗时 $t_{Total}$ 取决于耗时最长的区域，即：

$t_{Total} = \max\set{t_{1} , t_{2} , \cdots , t_{n}}$

为了加快开垦进度，顿顿准备在部分区域投入额外资源来缩短开垦时间，具体来说：
- 在第 $i$ 块区域每投入 $c_{i}$ 单位资源，便可将其开垦耗时缩短 $1$ 天
- 耗时缩短天数以整数记，即第 $i$ 块区域投入资源数量必须是 $c_{i}$ 的整数倍
- 在第 $i$ 块区域最多可投入 $c_{i} \times (t_{i} - k)$ 单位资源，将其开垦耗时缩短为 $k$ 天
- 这里的 $k$ 表示开垦一块区域的最少天数，满足 $\leq \min\set{t_{1} , t_{2} , \cdots ,t_{n}}$ ；换言之，如果无限制地投入资源，所有区域都可以用 $k$ 天完成开垦
现在顿顿手中共有 $m$ 单位资源可供使用，试计算开垦 $n$ 块区域最少需要多少天

输入格式

从标准输入读入数据
输入共 $n + 1$ 行
输入的第一行包含空格分隔的三个正整数 $n$ 、 $m$ 和 $k$ ，分别表示待开垦的区域总数、顿顿手上的资源数量和每块区域的最少开垦天数
接下来 $n$ 行，每行包含空格分隔的两个正整数 $t_{i}$ 和 $c_{i}$ ，分别表示第 $i$ 块区域开垦耗时和将耗时缩短 $1$ 天所需资源数量

输出格式

输出到标准输出
输出一个整数，表示开垦 $n$ 块区域的最少耗时

样例输入1

样例输出1

样例解释

如下表所示，投入 $5$ 单位资源即可将总耗时缩短至 $5$ 天，此时顿顿手中还剩余 $4$ 单位资源，但无论如何安排，也无法使总耗时进一步缩短

$i$	基础耗时	$t_{i}$ 缩减 $1$ 天所需资源	$c_{i}$ 投入资源数量	实际耗时
$1$	$6$	$1$	$1$	$5$
$2$	$5$	$1$	$0$	$5$
$3$	$6$	$2$	$2$	$5$
$4$	$7$	$1$	$2$	$5$

样例输入2

样例输出2

样例解释

投入 $20$ 单位资源，恰好可将所有区域开垦耗时均缩短为 $k = 2$ 天；受限于 $k$ ，剩余的 $10$ 单位资源无法使耗时进一步缩短

子任务

$70\%$ 的测试数据满足： $0 < n$ ， $t_{i}$ ， $c_{i} \leq 100$ 且 $\leq 10^{6}$
全部的测试数据满足： $0 < n$ ， $t_{i}$ ， $c_{i} \leq 10^{5}$ 且 $\leq 10^{9}$

`Python`实现

n, m, k = map(int, input().split())days = []
for _ in range(n):days.append(list(map(int, input().split())))def judge(x):sum = 0for i in range(n):if days[i][0] < x:continuesum += (days[i][0] - x) * days[i][1]if sum <= m:return Trueelse:return Falsel, r = k, max(days, key=lambda x: x[0])[0]while l <= r:mid = (l + r) // 2if judge(mid):r = mid - 1else:l = mid + 1print(l)