题目直达

1. 题目描述

有一个 m x n 大小的矩形蛋糕，需要切成 1 x 1 的小块。

给你整数 m ，n 和两个数组：

• horizontalCut 的大小为 m - 1 ，其中 horizontalCut[i] 表示沿着水平线 i 切蛋糕的开销。

• verticalCut 的大小为 n - 1 ，其中 verticalCut[j] 表示沿着垂直线 j 切蛋糕的开销。

一次操作中，你可以选择任意不是 1 x 1 大小的矩形蛋糕并执行以下操作之一：

1. 沿着水平线 i 切开蛋糕，开销为 horizontalCut[i] 。

2. 沿着垂直线 j 切开蛋糕，开销为 verticalCut[j] 。

每次操作后，这块蛋糕都被切成两个独立的小蛋糕。

每次操作的开销都为最开始对应切割线的开销，并且不会改变。

请你返回将蛋糕全部切成 1 x 1 的蛋糕块的 最小 总开销。

示例 1：

输入：m = 3, n = 2, horizontalCut = [1,3], verticalCut = [5]

输出：13

解释：

• 沿着垂直线 0 切开蛋糕，开销为 5 。

• 沿着水平线 0 切开 3 x 1 的蛋糕块，开销为 1 。

• 沿着水平线 0 切开 3 x 1 的蛋糕块，开销为 1 。

• 沿着水平线 1 切开 2 x 1 的蛋糕块，开销为 3 。

• 沿着水平线 1 切开 2 x 1 的蛋糕块，开销为 3 。

总开销为 5 + 1 + 1 + 3 + 3 = 13 。

示例 2：

输入：m = 2, n = 2, horizontalCut = [7], verticalCut = [4]

输出：15

解释：

• 沿着水平线 0 切开蛋糕，开销为 7 。

• 沿着垂直线 0 切开 1 x 2 的蛋糕块，开销为 4 。

• 沿着垂直线 0 切开 1 x 2 的蛋糕块，开销为 4 。

总开销为 7 + 4 + 4 = 15 。

提示：

• 1 <= m, n <= 10⁵

• horizontalCut.length == m - 1

• verticalCut.length == n - 1

• 1 <= horizontalCut[i], verticalCut[i] <= 10³

2. 分析

核心思路：优先队列(大根堆)+贪心

3. 代码

// 优先队列+贪心
type datas []int

func (dt datas) Less(i, j int) bool {
	// 大根
	return dt[i] > dt[j]
}

func (dt datas) Swap(i, j int) {
	dt[i], dt[j] = dt[j], dt[i]
}

func (dt datas) Len() int {
	return len(dt)
}

func (dt *datas) Pop() any {
	v := (*dt)[len(*dt)-1]
	*dt = (*dt)[:len(*dt)-1]
	return v
}

func (dt *datas) Push(v any) {
	*dt = append(*dt, v.(int))
}

type queue struct {
	datas *datas
}

func NewQueue() queue {
	datas := make(datas, 0, 10)
	return queue{
		datas: &datas,
	}
}

func (q *queue) IsEmpty() bool {
	return len(*q.datas) == 0
}

func (q *queue) Pop() int {
	return heap.Pop(q.datas).(int)
}

func (q *queue) Top() int {
	return (*q.datas)[0]
}

func (q *queue) Push(v int) {
	heap.Push(q.datas, v)
}

func minimumCost(m int, n int, horizontalCut []int, verticalCut []int) int64 {
	horizontalQueue := NewQueue()
	verticalQueue := NewQueue()
	for _, v := range horizontalCut {
		horizontalQueue.Push(v)
	}
	for _, v := range verticalCut {
		verticalQueue.Push(v)
	}
	// 初始：不论横竖切分，都是一行一列，只用切一次
	cols, rows := 1, 1
	var ret int64 = 0
	for {
		if verticalQueue.IsEmpty() && horizontalQueue.IsEmpty() {
			break
		}
		// 剩下的全部横切
		if verticalQueue.IsEmpty() {
			for !horizontalQueue.IsEmpty() {
				ret += int64(horizontalQueue.Pop() * cols)
			}
			break
		}
		// 剩下的全部竖切
		if horizontalQueue.IsEmpty() {
			for !verticalQueue.IsEmpty() {
				ret += int64(verticalQueue.Pop() * rows)
			}
			break
		}
		// 贪心，选择更大的一个先切
		// 5, 3  -> 15 , 3, 6 -> 15+18
		// 3, 5 -> 15, 5,4 -> 15+20
		// 横切
		if horizontalQueue.Top() >= verticalQueue.Top() {
			ret += int64(horizontalQueue.Pop() * cols)
			// 横切之后，行数+1
			rows++
			continue
		}
		// 竖切 verticaltop < horizontop
		ret += (int64(verticalQueue.Pop() * rows))
		cols++
	}
	return ret
}