题解 | #[NOIP2004]合并果子#
[NOIP2004]合并果子
https://ac.nowcoder.com/acm/problem/16663
技巧
堆（siftDown siftUp） 哈夫曼树模型
思路
模板题 。。。
实现
package main
import (
"bufio"
. "fmt"
"io"
"os"
)
func siftUp(heap []int, curr int) {
for curr != 0 && heap[curr] < heap[(curr-1)/2] {
heap[curr], heap[(curr-1)/2] = heap[(curr-1)/2], heap[curr]
curr = (curr - 1) / 2
}
}
func siftDown(h []int, root, last int) {
lc, rc := 2*root+1, 2*root+2
if lc < last {
min := root
if h[lc] < h[min] {
min = lc
}
if rc < last && h[rc] < h[min] {
min = rc
}
if min != root {
h[root], h[min] = h[min], h[root]
siftDown(h, min, last)
}
}
}
// https://ac.nowcoder.com/acm/problem/16663
func NC16663(_r io.Reader, _w io.Writer) {
in, out := bufio.NewReader(_r), bufio.NewWriter(_w)
defer out.Flush()
var n int
Fscan(in, &n)
heap := make([]int, n)
for i := 0; i < n; i++ {
Fscan(in, &heap[i])
siftUp(heap, i)
}
// 拿出两个数 合并 再塞回去
ans := 0
lastIndex := n - 1
for lastIndex != 0 {
a := heap[0]
heap[0] = heap[lastIndex]
siftDown(heap, 0, lastIndex)
lastIndex--
b := heap[0]
heap[0] = heap[lastIndex]
siftDown(heap, 0, lastIndex)
heap[lastIndex] = a + b
siftUp(heap, lastIndex)
ans += a + b
}
Fprintln(out, ans)
}
func main() {
NC16663(os.Stdin, os.Stdout)
}
