leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

1962.cpp (801B)

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