aboutsummaryrefslogtreecommitdiff
path: root/remove_stones.cpp
blob: f267b0cbdc0887ad4735b29e6bf700b30a734c9b (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
#include "leetcode.h"

class Solution {
public:
  int minStoneSum(vector<int> &piles, int k) {
    priority_queue<int> pq(piles.begin(), piles.end());
    int ans = accumulate(piles.begin(), piles.end(), 0);
    while (k--) {
      int i = pq.top();
      pq.pop();
      pq.push(i - i / 2);
      ans -= i / 2;
    }
    return ans;
  }
};

int main() {
  Solution obj;
  vector<int> piles1 = {5, 4, 9}, piles2 = {4, 3, 6, 7};
  cout << obj.minStoneSum(piles1, 2); // expect: 12
  cout << endl;
  cout << obj.minStoneSum(piles2, 3); // expect: 12
}