URL

Remove Stones to Minimize the Total - LeetCode

Code

https://github.com/syohex/dotnet-study/tree/master/fsharp/leetcode/problems/1962/main.fsx

#r "nuget:FSharpx.Collections"

open FSharpx.Collections

let minStoneSum (piles: int list) (k: int) : int =
    let rec sumQueue (q: IPriorityQueue<int>) acc : int =
        match (PriorityQueue.tryPop q) with
        | None -> acc
        | Some(v, q') -> sumQueue q' (v + acc)

    let rec minStoneSum' (q: IPriorityQueue<int>) (k: int) =
        if k = 0 then
            sumQueue q 0
        else
            let v, q' = PriorityQueue.pop q
            let q'' = PriorityQueue.insert (v - (v / 2)) q'
            minStoneSum' q'' (k - 1)

    let q =
        piles
        |> List.fold (fun acc n -> PriorityQueue.insert n acc) (PriorityQueue.empty true)

    minStoneSum' q k