aboutsummaryrefslogtreecommitdiff
path: root/other/remove_stones.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'other/remove_stones.cpp')
-rw-r--r--other/remove_stones.cpp24
1 files changed, 24 insertions, 0 deletions
diff --git a/other/remove_stones.cpp b/other/remove_stones.cpp
new file mode 100644
index 0000000..f267b0c
--- /dev/null
+++ b/other/remove_stones.cpp
@@ -0,0 +1,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
+}