3479. Fruits Into Baskets III
跟昨天那题题目一样
不过范围变大, 所以不能暴力解
思路：
根据题目, 可以把这题简化成
对每一个fruits[i], 找出所有值大于fruits[i]的basket
并且将fruits[i]放到其中index最小的basket
这样就先把basket按照大小排序, 用basketIdx记录原本的index经过排序后的顺序
接着用二分搜寻法找到j,basket[j]是第一个 >= fruit[i]的basket
假设basket长度是n, 找出 j ~ n 这个区间内, basketIdx中最小的值
阿要找区间最小值, 那就用segmentTree
找到记得把这个值mark起来, 以防重复使用 , 如果找不到的话, ans就+1
最后回传ans就好
golang code :
type segmentTree struct {
nums []int
array [][2]int
}
func buildTree(nums []int) *segmentTree {
n := len(nums)
array := make([][2]int, 4*n)
res := &segmentTree{nums, array}
res.build(0, 0, n-1)
return res
}
func (tree *segmentTree) build(node, l, r int) {
if r == l {
tree.array[node][0] = tree.nums[l]
tree.array[node][1] = l
return
}
m := l + (r-l)/2
tree.build(node*2+1, l, m)
tree.build(node*2+2, m+1, r)
if tree.array[2*node+1][0] > tree.array[2*node+2][0] {
tree.array[node][0], tree.array[node][1] = tree.array[2*node+2][0], tree.
array[2*node+2][1]
} else {
tree.array[node][0], tree.array[node][1] = tree.array[2*node+1][0], tree.
array[2*node+1][1]
}
}
func (tree *segmentTree) query(node, boundaryL, boundaryR, queryL, queryR int)
(int, int) {
if boundaryL > queryR || boundaryR < queryL {
return math.MaxInt64, -1
}
if boundaryL >= queryL && boundaryR <= queryR {
return tree.array[node][0], tree.array[node][1]
}
boundaryM := boundaryL + (boundaryR-boundaryL)/2
a, idxL := tree.query(node*2+1, boundaryL, boundaryM, queryL, queryR)
b, idxR := tree.query(node*2+2, boundaryM+1, boundaryR, queryL, queryR)
if a < b {
return a, idxL
}
return b, idxR
}
func (tree *segmentTree) modify(node, idx, val, l, r int) {
if l == r {
tree.array[node][0] = val
return
}
m := l + (r-l)/2
if idx <= m {
tree.modify(node*2+1, idx, val, l, m)
} else {
tree.modify(node*2+2, idx, val, m+1, r)
}
if tree.array[2*node+1][0] > tree.array[2*node+2][0] {
tree.array[node][0], tree.array[node][1] = tree.array[2*node+2][0], tree.
array[2*node+2][1]
} else {
tree.array[node][0], tree.array[node][1] = tree.array[2*node+1][0], tree.
array[2*node+1][1]
}
}
func numOfUnplacedFruits(fruits []int, baskets []int) int {
n := len(fruits)
basketsIdx, baskets2 := make([]int, n), make([]int, n)
for i := 0; i < n; i++ {
basketsIdx[i] = i
}
ans := 0
slices.SortFunc(basketsIdx, func(a, b int) int { return baskets[a] - baskets[
b] })
for idx := range basketsIdx {
baskets2[idx] = baskets[basketsIdx[idx]]
}
tree := buildTree(basketsIdx)
for _, fruitNum := range fruits {
idx := sort.SearchInts(baskets2, fruitNum)
if idx < n {
tmp, changedIdx := tree.query(0, 0, n-1, idx, n-1)
if tmp != math.MaxInt64 {
ans++
tree.modify(0, changedIdx, math.MaxInt64, 0, n-1)
}
}
}
return n - ans
}

卷够没