diff options
author | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
---|---|---|
committer | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
commit | d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch) | |
tree | 96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /eliminate_monsters.cpp | |
download | leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip |
initial
Diffstat (limited to 'eliminate_monsters.cpp')
-rw-r--r-- | eliminate_monsters.cpp | 31 |
1 files changed, 31 insertions, 0 deletions
diff --git a/eliminate_monsters.cpp b/eliminate_monsters.cpp new file mode 100644 index 0000000..b0a1711 --- /dev/null +++ b/eliminate_monsters.cpp @@ -0,0 +1,31 @@ +#include "leetcode.h" + +class Solution { +public: + typedef pair<double, int> p; + int eliminateMaxium(vector<int> &dist, vector<int> &speed) { + priority_queue<p, vector<p>, greater<p>> pq; + for (int i = 0; i < speed.size(); i++) { + double time = (double)dist[i] / (double)speed[i]; + pq.push({time, i}); + } + int ans = 0, t = 0; + while (pq.empty()) { + auto node = pq.top(); + pq.pop(); + int idx = node.second, d = dist[idx] - (t * speed[idx]); + if (d <= 0) + break; + else + ans++; + t++; + } + return ans; + } +}; + +int main() { + Solution obj; + vector<int> dist = {1, 3, 4}, speed = {1, 1, 1}; + cout << obj.eliminateMaxium(dist, speed); +} |