题面描述

在一次火锅聚餐中，你可以选择不同的菜品，每种菜品在下锅后需要特定的时间才能变得刚好合适。为了尽可能多地享用这些刚好合适的菜品，你的捞取速度受到限制，每次捞取后需要间隔至少$m$秒才能再次捞取。给定$n$种菜品的信息，每种菜品在$x$秒下锅后需要$y$秒才能变得刚好合适。请计算在最合理的策略下，最多能捞取到多少种刚好合适的菜品。输入包含两个整数$n$和$m$，接下来的$n$行每行包含两个整数$x$和$y$。输出一个整数，表示最多能吃到的刚好合适的菜品数量。

思路

贪心。我们采用贪心策略，首先将所有菜按照它们刚好合适的时间即$t = x + y$进行排序，然后依次选择可以捞取的菜，确保每次捞取之间至少间隔$m$秒。

贪心证明:

假设存在一个最优解序列$O$，其捞取的菜品数量为最大值。设贪心算法选择的第一个菜品与最优解$O$中选择的第一个菜品不同。假设贪心算法选择的第一个菜品的时间为$t_g$，而最优解选择的第一个菜品的时间为$t_o$，且$t_g < t_o$。

由于$t_g < t_o$，在贪心算法选择$t_g$后，剩余的菜品选择不会因为选择了$t_g$而比选择$t_o$少。我们可以将最优解$O$中的$t_o$替换为$t_g$，而不会影响后续选择的可能性，因为$t_g$更早或相同时间可用，依然满足间隔$m$秒的约束。因此，通过这样的交换，最优解$O$仍然保持最大数量的菜品被捞取。

重复上述交换过程，最终可将最优解转换为贪心算法的选择序列，而不减少捞取的菜品数量。因此，贪心策略选择最早刚好合适且满足间隔$m$秒的菜品序列必然是最优解。

cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    int n, m;
    cin >> n >> m;
    // 存储每个菜的刚好合适的时间
    vector<int> t(n);
    for(int i=0;i<n;i++){
        int x, y;
        cin >> x >> y;
        t[i] = x + y;
    }
    // 按照时间排序
    sort(t.begin(), t.end());
    int count = 0;
    int last = -1000000; // 初始化为一个很小的值
    for(int i=0;i<n;i++){
        if(t[i] >= last + m){
            count++;
            last = t[i];
        }
    }
    cout << count;
    return 0;
}

python

def main():
    n, m = map(int, input().split())
    # 存储每个菜的刚好合适的时间
    t = []
    for _ in range(n):
        x, y = map(int, input().split())
        t.append(x + y)
    
    # 按照时间排序
    t.sort()
    count = 0
    last = -1000000  # 初始化为一个很小的值
    
    for time in t:
        if time >= last + m:
            count += 1
            last = time
    
    print(count)

if __name__ == "__main__":
    main()

java

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        
        // 存储每个菜的刚好合适的时间
        int[] t = new int[n];
        for (int i = 0; i < n; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            t[i] = x + y;
        }
        
        // 按照时间排序
        Arrays.sort(t);
        int count = 0;
        int last = -1000000; // 初始化为一个很小的值
        
        for (int time : t) {
            if (time >= last + m) {
                count++;
                last = time;
            }
        }
        
        System.out.println(count);
        scanner.close();
    }
}

题目内容

入职后，导师会请你吃饭，你选择了火锅。

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

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

你希望吃到最多的刚好合适的菜，但你的手速不够快，用 $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

说明

一共下了两个菜，在第一秒下的菜需要到第三秒吃，在第二秒下的菜也要到第三秒吃，所以只能吃一个

样例2

输入

3 1
1 2
1 3
2 3

输出

3

说明

一共下了两个菜，可以每秒捞一个，第一个在第一秒下的菜需要到第3秒吃，第二个在第一秒下的菜需要到第4秒吃，在第二秒下的菜也要到第5秒吃，所以三个都能吃到