导师请吃火锅

题目描述

入职后, 导师会请你吃饭, 你选择了火锅.

火锅里会在不同时间下很多菜.

不同食材要煮不同的时间, 才能变得刚好合适.

你希望吃到最多的刚好合适的菜, 但你的手速不够快, 用m代表手速, 每次下手捞菜后至少要过m秒才能再捞, 每次只能捞一个.

那么用最合理的策略, 最多能吃到多少刚好合适的菜?

输入描述

第一行两个整数n, m, 其中n代表往锅里下的菜的个数, m代表手速, 1 < n, m < 1000.

接下来有n行, 每行有两个数x, y代表第x秒下的菜过y秒才能变得刚好合适, 1 < x, y < 1000.

输出描述

输出一个整数代表用最合理的策略, 最多能吃到刚好合适的菜的数量.

示例1

输入:

2 1
1 2
2 1

输出:

1

题解

Python

import sys

def main():
    # 先读取输入
    parts = input().split()
    assert len(parts) == 2
    # 菜的个数
    n = int(parts[0])
    # 手速
    m = int(parts[1])

    # 放菜的策略, 每个菜可以食用的时间点
    times = []
    for line in sys.stdin.readlines():
        start, delay = list(map(int, line.split()))
        time = start + delay
        times.append(time)
    assert len(times) == n

    # 每个时间点可以吃的菜的个数, 初始化为0
    # 注意, 时间点是从1开始计数的, 我们这里要从0开始
    food_nums = [0] * (max(times) + 1)
    for time in times:
        # 这个时间点有菜
        food_nums[time] += 1

    # 记录每种策略下可以吃到的菜的数量, 最后从中选择最大值就行
    eat_food = []

    # DFS 查找当前时间点可以吃的菜的数量
    def dfs(time, current_food):
        # 超过最大时间点, 后面没菜了, 终止递归
        if time >= len(food_nums):
            # 当前策略下吃到的所有的菜
            eat_food.append(current_food)
            return
        elif food_nums[time] > 0:
            # 当前时间点有菜, 有两个策略:
            # 1. 直接吃, 然后等待m秒
            dfs(time + m, current_food + 1)
            # 2. 不吃, 去到下个时间点吃
            dfs(time + 1, current_food)
        else:
            # 当前时间点没有菜, 去下个时间点
            dfs(time + 1, current_food)

    # 从第1个时间点开始进行递归搜索
    dfs(1, 0)
    
    # 打印可以吃到的最多的菜
    print(max(eat_food))

if __name__ == "__main__":
    main()