【贪心】2024E-吃火锅

[P3120] 【贪心】2024E-吃火锅

本题练习地址：https://www.algomooc.com/problem/P3120

直播回看地址：2023/11/18 真题讲解

题目描述与示例

题目描述

入职后，导师会请你吃饭，你选择了火锅。火锅里会在不同时间下很多菜，不同食材要煮不同时间，才能变得刚好合适，你希望吃到最多的刚好合适的菜，但是你的手速不够快，用m代替手速，即每次下手捞菜后至少要过m秒才能再捞（每次只能捞一个），那么用最合理的策略，最多能吃到多少刚好合适的菜。

输入描述

第一行两个整数n，m。其中n代表往锅里下菜的个数，m代表手速。

接下来有n行，每行有两个数x，y。代表第x秒下的菜过y秒才能变得刚好合适

（1 < m, n < 1000），（1 < x, y < 1000）

输出描述

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

示例一

输入

2 1
1 2
2 1

输出

说明

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

示例二

输入

输出

说明

一共下了三个菜，每秒捞一个，第一个在第一秒下的菜，需要到第三秒吃，第二个在第一秒下的菜需要到第四秒吃，在第二秒下的菜，需要到第五秒吃，所以三个都能吃。

解题思路

在本题中，每道菜的下锅时间x和煮熟时间y其实并不重要，我们关心的是某个菜刚好合适的时间t。

每一个菜都可以计算出其刚好合适的时间ti = xi + yi，然后我们对时间所有的ti进行从小到大排序，得到所有菜刚好合适吃的时间所构成的列表dish_time_list。

然后维护一个变量pre_time表示上一次吃菜时间，贪心地从头遍历dish_time_list中的所有时间t，一旦发现t - pre_time >= m，成立，则立马选择吃菜，更新ans和pre_time。核心代码如下

for t in dish_time_list:
    if t - pre_time >= m:
        ans += 1
        pre_time = t

可以考虑一个简单的例子来思考为什么这样的贪心策略是可行的。假设手速m = 2，有三道菜恰好能吃的时间是dish_time_list = [2, 3, 4]，为了尽可能多地吃到菜，我们肯定希望前一次吃下的时间尽可能地提前，因此会选择t = 2的菜而不是t = 3的菜来进行食用。

代码

Python

# 题目：【贪心】2024E-吃火锅
# 分值：200
# 作者：许老师-闭着眼睛学数理化
# 算法：贪心
# 代码看不懂的地方，请直接在群上提问


# 输入菜数n，手速m
n, m = map(int, input().split())

# 创建列表dish_time_list，
# 储存每一个菜，刚刚好能吃的时间
dish_time_list = list()

# 循环n次，输入下菜时间x和煮菜时长y
for _ in range(n):
    x, y = map(int, input().split())
    # 两者相加，为这个菜刚刚好能吃的时间
    dish_time_list.append(x+y)

# 从小到大排序
dish_time_list.sort()

# 初始化答案变量ans和上一次吃菜的时间pre_time
ans = 0
pre_time = -m

# 遍历dish_time_list中的每一个时间，贪心地进行选择
# 只要满足间隔m的条件，就直接进行选择
for t in dish_time_list:
    # 如果当前某个菜刚好合适，而且距离上次吃菜的时间超过了手速m
    # 那么直接选择这个菜，更新答案变量，且修改pre_time变量
    # 表示对于下一次吃菜，当前的t成为了其上一次吃菜时间pre_time
    if t - pre_time >= m:
        ans += 1
        pre_time = t

print(ans)

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int m = scanner.nextInt();

        List<Integer> dishTimeList = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            dishTimeList.add(x + y);
        }

        Collections.sort(dishTimeList);

        int ans = 0;
        int preTime = -m;

        for (int t : dishTimeList) {
            if (t - preTime >= m) {
                ans++;
                preTime = t;
            }
        }

        System.out.println(ans);
    }
}

C++

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

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<int> dishTimeList;

    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        dishTimeList.push_back(x + y);
    }

    sort(dishTimeList.begin(), dishTimeList.end());

    int ans = 0;
    int preTime = -m;

    for (int t : dishTimeList) {
        if (t - preTime >= m) {
            ans++;
            preTime = t;
        }
    }

    cout << ans << endl;

    return 0;
}

时空复杂度

时间复杂度：O(NlogN)。排序所需的时间复杂度。

空间复杂度：O(1)。忽略排序所需的栈空间，仅需若干常数变量。