Sponsored
Sponsored
This approach involves computing the exact time each monster will take to reach the city and then eliminating them in the order of their arrival times. The goal is to eliminate as many monsters as possible before any monster reaches the city.
Time Complexity: O(n log n) due to sorting the times.
Space Complexity: O(n) to store the arrival times.
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5int eliminateMaximum(std::vector<int>& dist, std::vector<int>& speed) {
6 std::vector<int> time;
7 for (int i = 0; i < dist.size(); ++i) {
8 time.push_back((dist[i] + speed[i] - 1) / speed[i]); // ceiling of (dist[i] / speed[i])
9 }
10 std::sort(time.begin(), time.end());
11 for (int i = 0; i < time.size(); ++i) {
12 if (time[i] <= i) {
13 return i;
14 }
15 }
16 return time.size();
17}
18
19int main() {
20 std::vector<int> dist = {1, 3, 4};
21 std::vector<int> speed = {1, 1, 1};
22 int result = eliminateMaximum(dist, speed);
23 std::cout << result << std::endl;
24 return 0;
25}The C++ solution operates similarly to the C solution. It leverages the STL to sort the arrival times. If the index of the iteration through these times reaches or surpasses the arrival time, the process stops, representing a loss condition.
This approach improves the efficiency of eliminating the maximum number of monsters by using a binary search method. It pre-calculates when a monster will reach the city and uses efficient search techniques to make decisions dynamically during the elimination process.
Time Complexity: O(n log n) due to the sort operation.
Space Complexity: O(n) to store arrival times.
1from bisect import bisect_right
2
3def eliminateMaximum
By using a library function like bisect_right in Python, the code finds the largest index to insert a value (in this case to simulate minutes passing) while maintaining order. This efficiently tells us the maximum monsters that can be eliminated as time progresses.