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

文章目录

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

试题编号

试题名称

时间限制

内存限制

问题描述

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

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$块区域每投入$c_i$单位资源，便可将其开垦耗时缩短$1$天
  • 耗时缩短天数以整数记，即第$i$块区域投入资源数量必须是$c_i$的整数倍
  • 在第$i$块区域最多可投入$c_i\times (t_i-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$天完成开垦
• 现在顿顿手中共有$m$单位资源可供使用，试计算开垦$n$块区域最少需要多少天

输入格式

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

输出格式

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

样例输入1

4 9 2
6 1
5 1
6 2
7 1

样例输出1

5

样例解释

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

样例输入2

4 30 2
6 1
5 1
6 2
7 1

样例输出2

2

样例解释

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

子任务

• $70\%$的测试数据满足：$0<n$，$t_i$，$c_i\le 100$且$0<m\le 10^6$
• 全部的测试数据满足：$0<n$，$t_i$，$c_i\le 10^5$且$0<m\le 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 = 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)