aboutsummaryrefslogtreecommitdiff
path: root/remove_stones.rs
diff options
context:
space:
mode:
Diffstat (limited to 'remove_stones.rs')
-rw-r--r--remove_stones.rs26
1 files changed, 26 insertions, 0 deletions
diff --git a/remove_stones.rs b/remove_stones.rs
new file mode 100644
index 0000000..e55eade
--- /dev/null
+++ b/remove_stones.rs
@@ -0,0 +1,26 @@
+use std::collections::BinaryHeap;
+struct Solution;
+
+impl Solution {
+ pub fn min_stone_sum(piles: Vec<i32>, mut k: i32) -> i32 {
+ let mut max_heap = BinaryHeap::<i32>::new();
+ for i in piles {
+ max_heap.push(i);
+ }
+ while k > 0 {
+ if let Some(top) = max_heap.pop() {
+ let removed = top - top / 2;
+ max_heap.push(removed);
+ }
+ k -= 1;
+ }
+ max_heap.iter().sum()
+ }
+}
+
+fn main() {
+ let piles1 = vec![5,4,9];
+ let piles2 = vec![4,3,6,7];
+ println!("{}", Solution::min_stone_sum(piles1, 2)); //expect: 12
+ println!("{}", Solution::min_stone_sum(piles2, 3)); //expect: 12
+}