#P3241. 火锅(200分)
-
1000ms
Tried: 90
Accepted: 39
Difficulty: 7
所属公司 :
华为od
火锅(200分)
题面描述
在一次火锅聚餐中,你可以选择不同的菜品,每种菜品在下锅后需要特定的时间才能变得刚好合适。为了尽可能多地享用这些刚好合适的菜品,你的捞取速度受到限制,每次捞取后需要间隔至少m秒才能再次捞取。给定n种菜品的信息,每种菜品在x秒下锅后需要y秒才能变得刚好合适。请计算在最合理的策略下,最多能捞取到多少种刚好合适的菜品。输入包含两个整数n和m,接下来的n行每行包含两个整数x和y。输出一个整数,表示最多能吃到的刚好合适的菜品数量。
思路
贪心。我们采用贪心策略,首先将所有菜按照它们刚好合适的时间即t=x+y进行排序,然后依次选择可以捞取的菜,确保每次捞取之间至少间隔m秒。
贪心证明:
假设存在一个最优解序列O,其捞取的菜品数量为最大值。设贪心算法选择的第一个菜品与最优解O中选择的第一个菜品不同。假设贪心算法选择的第一个菜品的时间为tg,而最优解选择的第一个菜品的时间为to,且tg<to。
由于tg<to,在贪心算法选择tg后,剩余的菜品选择不会因为选择了tg而比选择to少。我们可以将最优解O中的to替换为tg,而不会影响后续选择的可能性,因为tg更早或相同时间可用,依然满足间隔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秒吃,所以三个都能吃到