leetcode

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