1 题目介绍

题目地址：垦田计划
注意：需要账号登录。

题目介绍就直接贴原题了。

2 题目分析

这个题目，我一开始就是想到的就是枚举，首先，将这些地按需要的天数从大到小排序，然后从左向右找一块地：这块地需满足，在资源允许的情况下，让比这块地需要天数多的，降到跟这块地一样的天数。随后的情况就比较简单了，在对剩余的资源进行判断，这些地是否能同时进行降天数，这就够了。
刚开始没有考虑到时间的问题，就从左（-1）向右一个个找了，最后，只通过了70%。

后来，就对代码进行了优化，在找下标的时候有二分来进行找，降低了时间复杂度，后来就过了。

3 代码

两次的代码都放在下面了，方便参考对照。

• 开始代码

n, m, k = map(int, input().split())
li = []
for i in range(n):
    li.append([int(j) for j in input().split()])
li = sorted(li, key=lambda x:x[0], reverse=True)

t = -1 # 判断能满足最小的天数的下表
while True:
    min_day = li[t][0]
    # 判断前面大的天数变为目前最小的天数所需要的资源
    s1 = 0
    for day in li[:t]:
        s1 += (day[0]-min_day) * day[1]
    if s1 > m:
        t -= 1
        continue
    # s1 <= m
    # 找到了可以将其变为最小的天数 此时最大的天数就为min_day=li[t][0]
    """
    不确定是否剩余的资源能否使继续降
    """
    # 更新资源
    m = m - s1
    # 存储li[:t+1]这些天，一起降1天需要的资源，这些天的天数已经全是min_day=li[t][0], 看是否还能降，最多不能小于k
    s2 = 0
    # 情况一
    if t == -1:
        for day in li:
            s2 += day[1]
    # 情况二
    else:
        for day in li[:t+1]:
            s2 += day[1]
    if m < s2:
        break
    # m >= s2
    delete_day = m // s2
    min_day = min_day - delete_day
    # 这是针对情况一的，情况二没有可能会低于k
    if min_day < k:
        min_day = k
    break

print(min_day)

• 最终代码

n, m, k = map(int, input().split())
li = []
for i in range(n):
    li.append([int(j) for j in input().split()])
# 按天数从大到小排。
li = sorted(li, key=lambda x:x[0], reverse=True)

# t = -1 # 判断能满足最小的天数的下标
# 由于对于30%的数据超时了，改成二分找下标
left = -n
right = -1
t = (left + right) // 2
flag = True
while True:
    min_day = li[t][0]
    # 判断前面大的天数变为目前最小的天数所需要的资源
    s1 = 0
    for day in li[:t]:
        s1 += (day[0]-min_day) * day[1]
    # 对于量大的30%的数据超时了
    # 改成二分找t
    if left != right and flag:
        temp = t
        if s1 > m:
            right = t
            t = (left + right) // 2
            continue
        else:
            left = t
            t = (left + right) // 2
            if t == temp:
                flag = False
                t += 1
            continue
    
    if s1 > m:
        t -= 1
        continue
    # s1 <= m
    # 找到了可以将其变为最小的天数 此时最大的天数就为min_day=li[t][0]
    # 更新资源
    m = m - s1
    # 存储li[:t+1]这些天，一起降1天需要的资源，这些天的天数已经全是min_day=li[t][0], 看是否还能降，最多不能小于k
    s2 = 0
    # 情况一
    if t == -1:
        for day in li:
            s2 += day[1]
    # 情况二
    else:
        for day in li[:t+1]:
            s2 += day[1]
    if m < s2:
        break
    # m >= s2
    delete_day = m // s2
    min_day = min_day - delete_day
    # 这是针对情况一的，情况二没有可能会低于k
    if min_day < k:
        min_day = k
    break

print(min_day)

4 结语

我的解题代码并不一定是最优解，单纯是分享一下，我的解题思路，像这道题还可以用贪心来解。
这个是计算机学会的官方解题讲解：第29次CCF CSP认证题目精讲
可以去学习、学习。