aboutsummaryrefslogtreecommitdiff
path: root/remove_stones.rs
blob: e55eadeee56171bca87f99d0c5424e377bd1e0e2 (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
25
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
}