leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1962.cpp (801B)

      1 // Using a priority_queue
      2 class Solution {
      3   public:
      4     int minStoneSum(vector<int> &piles, int k) {
      5         priority_queue<int> pq;
      6         int res = 0;
      7         for (int e : piles)
      8             res += e, pq.push(e);
      9         while (k--) {
     10             int t = pq.top(), pq.pop();
     11             pq.push(t - t / 2), res -= t / 2;
     12         }
     13         return res;
     14     }
     15 };
     16 
     17 // Using heap, constant memory
     18 class Solution {
     19   public:
     20     int minStoneSum(vector<int> &piles, int k) {
     21         auto b = piles.begin(), e = piles.end();
     22         make_heap(b, e);
     23         while (k--) {
     24             pop_heap(b, e);
     25             auto &elem = *(e - 1);
     26             elem -= elem / 2;
     27             push_heap(b, e);
     28         }
     29         int sum = 0;
     30         for (auto v : piles)
     31             sum += v;
     32         return sum;
     33     }
     34 };