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);
}
|