题解 | #[NOIP2004]合并果子#

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)
}