3066: Minimum-Operations-to-Exceed-Threshold-Value-II
Medium
Where did all my beloved string manipulation questions go?! Slight disaster, but it is a-ok, since today’s question is a priority_queue question.
Starting off, we know we can ignore all the values
greater than k as they already
satisfy the pre-requisite. This means we can start off by
pre-computing all the values that are
smaller than k as they are the only
relevant values needed to solve this
question.
Consequently, once we do pre-compute all the relevant
values, the only way to possibly count the
minimum number of the previously described
operation is if we just… repeat the operation… over and over
again… yeah, not the fanciest solution ever. However, the
most efficient data-structure for this question is a
priority_queue (or a min heap) as at
every step, we have to retrieve the 2 smallest
values and re-insert the new calculated
value back into the list while maintaining
the same order (a task perfect for a
priority_queue).
Therefore, you just repeat the operation, until the
priority_queue is empty or has size equal to
1 (whilst keeping a counter ans of all
the operations that have been initialized)
Code:
class Solution {
public:
int minOperations(vector<int>& nums, int k) {
priority_queue<int, vector<int>, greater<int>> valid;
for (int &n : nums) {
if (n < k) {
valid.push(n);
}
}
if (valid.size() == 0) return 0;
int ans = 0;
while (valid.size() > 1) {
++ans;
int min1 = valid.top();
valid.pop();
int min2 = valid.top();
valid.pop();
int new_value = min1 + min2;
if (new_value >= k) continue;
new_value += min1;
if (new_value >= k) continue;
else {
valid.push(new_value);
}
}
return valid.size() == 1 ? ans + 1 : ans;
}
};