CF1310A Recommendations 题解

灵茶山艾府 · 2022-05-26 13:39:47 · 题解

按 a[i] 从小到大遍历，把 a[i] 相同的元素分为一组。

比如 a=[1,1,1,2,9,9]，那么一开始把等于 1 的元素的花费丢到一个大根堆中，其中有一个 1 是不需要增大的，把最大的花费弹出，表示对应的那个 1 不需要增大。

然后把等于 2 的元素的花费丢到大根堆中，同样把最大的花费弹出，表示对应的那个元素不需要继续增大。

然后把等于 3 的元素的花费丢到大根堆中，由于此时没有等于 3 的元素，直接从堆中弹出一个最大的花费。

模拟上述过程，同时用一个变量 \textit{costSum} 表示堆中的花费之和，每次弹出最大花费后，累加 \textit{costSum}，即为答案。

AC 代码（Golang）：

package main
import("bufio";"container/heap";."fmt";"os";"sort")

func main() {
    in := bufio.NewReader(os.Stdin)
    var n int
    Fscan(in, &n)
    a := make([]struct{ v, t int }, n)
    for i := range a { Fscan(in, &a[i].v) }
    for i := range a { Fscan(in, &a[i].t) }
    sort.Slice(a, func(i, j int) bool { return a[i].v < a[j].v })

    ans := int64(0)
    h := hp{}
    for i, cur, costSum := 0, 0, int64(0); i < n || h.Len() > 0; cur++ {
        if h.Len() == 0 { cur = a[i].v }
        for ; i < n && a[i].v == cur; i++ { // 所有等于 cur 的元素的花费入堆
            heap.Push(&h, a[i].t)
            costSum += int64(a[i].t)
        }
        costSum -= int64(heap.Pop(&h).(int)) // 弹出一个最大花费，表示这个元素不需要继续增大
        ans += costSum
    }
    Print(ans)
}

type hp struct{ sort.IntSlice }
func (h hp) Less(i, j int) bool  { return h.IntSlice[i] > h.IntSlice[j] }
func (h *hp) Push(v interface{}) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() interface{}   { a := h.IntSlice; v := a[len(a)-1]; h.IntSlice = a[:len(a)-1]; return v }