-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy patheliminate-maximum-number-of-monsters_1921.cpp
105 lines (78 loc) · 2.57 KB
/
eliminate-maximum-number-of-monsters_1921.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
/*
https://leetcode.com/problems/eliminate-maximum-number-of-monsters/submissions/1094419012
Runtime
Details
104ms
Beats 77.33%of users with C++
Memory
Details
81.35MB
Beats 95.73%of users with C++
https://leetcode.com/problems/eliminate-maximum-number-of-monsters/submissions/1094417853
Runtime
Details
111ms
Beats 55.20%of users with C++
Memory
Details
81.28MB
Beats 97.87%of users with C++
*/
class Solution {
public:
int eliminateMaximum(std::vector<int> &dist, std::vector<int> &speed) {
// Use std::transform with a lambda function to calculate arrival times
std::transform(dist.begin(), dist.end(), speed.begin(), dist.begin(),
[](int d, int s) { return (d + s - 1) / s; });
// Sort the arrival times.
std::sort(dist.begin(), dist.end());
// Try to eliminate each monster one by one.
for (int i = 0; i < dist.size(); ++i) {
// If a monster arrives before or when we are eliminating, we can't
// eliminate all.
if (dist[i] <= i) {
return i; // The number of monsters eliminated before one
// reaches us.
}
}
// If we've processed all monsters without returning, we can eliminate
// all of them.
return dist.size();
}
};
/*
https://leetcode.com/problems/eliminate-maximum-number-of-monsters/submissions/1093489124?envType=daily-question&envId=2023-11-07
Runtime
Details
111ms
Beats 54.67%of users with C++
Memory
Details
83.26MB
Beats 80.80%of users with C++
*/
class Solution {
public:
int eliminateMaximum(std::vector<int> &dist, std::vector<int> &speed) {
std::vector<int> arrivalTimes(dist.size());
// Calculate the arrival time for each monster.
for (int i = 0; i < dist.size(); ++i) {
// Ceiling of dist/speed to get the arrival time
arrivalTimes[i] = (dist[i] + speed[i] - 1) / speed[i];
}
// Sort the arrival times.
std::sort(arrivalTimes.begin(), arrivalTimes.end());
// Try to eliminate each monster one by one.
for (int i = 0; i < arrivalTimes.size(); ++i) {
// If a monster arrives before or when we are eliminating, we can't
// eliminate all.
if (arrivalTimes[i] <= i) {
return i; // The number of monsters eliminated before one
// reaches us.
}
}
// If we've processed all monsters without returning, we can eliminate
// all of them.
return arrivalTimes.size();
}
};