aboutsummaryrefslogtreecommitdiff
path: root/eliminate_monsters.cpp
blob: b0a171177e42903c9a1978a41f0fd27cf111dd61 (plain)
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
#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);
}