E-导师请吃火锅(100p)

导师请吃火锅

问题描述

入职后，导师邀请你共进火锅。火锅中会在不同时间下入各种食材。每种食材都有其最佳烹饪时间，只有在恰到好处的时候才能品尝到最佳口感。你希望能吃到最多的恰到好处的菜品，但你的手速有限，用 表示你的手速，即每次捞菜后至少要等待 秒才能再次下手（每次只能捞一个）。请计算在最优策略下，你最多能吃到多少个恰到好处的菜品。

输入格式

第一行包含两个整数 和 ，分别表示下入火锅的菜品数量和你的手速（即两次捞菜之间的最小间隔时间）。

接下来的 行，每行包含两个整数 和 ，表示在第 秒下入的菜品在 秒后变得恰到好处。

输出格式

输出一个整数，表示在最优策略下能吃到的恰到好处的菜品数量。

样例输入1

2 1
1 2
2 1

样例输出1

1

样例输入2

3 2
1 2
2 4
5 1

样例输出2

2

样例解释

数据范围

题解

贪心

这道题目本质上是一个贪心算法问题。关键在于理解我们需要在保证手速限制的情况下，尽可能多地捞取恰到好处的菜品。解题思路如下：

1. 首先，我们需要计算每个菜品变得恰到好处的时间（下锅时间 + 烹饪时间）。

2. 将所有菜品按照变得恰到好处的时间排序。这样可以保证我们按时间顺序处理每个菜品。

3. 我们总是捞取第一个恰到好处的菜品，因为这是最优的开始策略。

4. 对于后续的每个菜品，我们需要判断是否可以捞取。判断的依据是：

   • 当前菜品变得恰到好处的时间是否晚于或等于上一次捞菜的时间加上手速限制。

5. 如果可以捞取，我们就捞起这个菜品，并更新上一次捞菜的时间索引。

6. 最后，统计总共捞起的菜品数量。

参考代码

以下是基于您提供的代码重构后的参考代码，包括五种语言的实现：

• Python

def getResult(n, m, suit_times):
    # 按照菜品变得恰到好处的时间排序
    suit_times.sort()
    
    count = 1  # 第一个合适的菜必定会捞
    last_picked = 0  # 上一次捞菜的索引
    
    for i in range(1, n):
        # 如果当前菜品可以捞（满足时间间隔要求）
        if suit_times[i] >= suit_times[last_picked] + m:
            count += 1
            last_picked = i  # 更新上一次捞菜的索引
    
    return count

# 输入处理
n, m = map(int, input().split())
suit_times = []
for _ in range(n):
    x, y = map(int, input().split())
    suit_times.append(x + y)

# 输出结果
print(getResult(n, m, suit_times))

• C

#include <stdio.h>
#include <stdlib.h>

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int getResult(int n, int m, int* suit_times) {
    qsort(suit_times, n, sizeof(int), compare);
    
    int count = 1;  // 第一个合适的菜必定会捞
    int last_picked = 0;  // 上一次捞菜的索引
    
    for (int i = 1; i < n; i++) {
        if (suit_times[i] >= suit_times[last_picked] + m) {
            count++;
            last_picked = i;
        }
    }
    
    return count;
}

int main() {
    int n, m;
    scan