Re: [閒聊] 每日leetcode
哎喲 我肏
這題怎麼這麼難, 寫到現在 幹幹幹
3454. Separate Squares II
跟昨天不同, 今天的題目, 重疊的面積只能算一次
思路 :
用segment tree紀錄目前x軸累積的寬度
首先把每個正方形拆成兩個平行x軸的邊稱為上邊、下邊
並且以[x1,x2,y,k]的形式記錄起來, 其中k是用來記錄這是上邊還是下邊
並且依照y的大小排序
當遇到下邊時, 要把下邊這段長度(x2-x1)加到累積寬度裡
反之遇到上邊, 要把上邊的長度扣掉
就這樣遍歷所有邊
每次都將 累積的寬度*(目前邊的y-上一條邊的y) 加到面積裡
算出總面積後
再從頭算一次
這次算到面積 >= 總面積的一半後
將 目前的y - ( 目前的面積 - 總面積的一半後 ) / 累積寬度就是答案
golang code :
type Node struct {
l, r int
k int
length int
}
type SegmentTree struct {
nums []int
tree []Node
}
func newTree(nums []int) *SegmentTree {
n := len(nums)
t := make([]Node, 4*n)
s := &SegmentTree{
nums: nums,
tree: t,
}
s.build(0, 0, n-1)
return s
}
func (t *SegmentTree) build(u, l, r int) {
t.tree[u].l = l
t.tree[u].r = r
if l != r {
mid := l + (r-l)/2
t.build(u*2+1, l, mid)
t.build(u*2+2, mid+1, r)
}
}
func (t *SegmentTree) modify(u, l, r, k int) {
if t.tree[u].l > r || t.tree[u].r < l {
return
}
if l <= t.tree[u].l && t.tree[u].r <= r {
t.tree[u].k += k
} else {
mid := t.tree[u].l + (t.tree[u].r-t.tree[u].l)/2
if l <= mid {
t.modify(u*2+1, l, r, k)
}
if r > mid {
t.modify(u*2+2, l, r, k)
}
}
if t.tree[u].k > 0 {
t.tree[u].length =
t.nums[t.tree[u].r+1] - t.nums[t.tree[u].l]
} else if t.tree[u].l == t.tree[u].r {
t.tree[u].length = 0
} else {
t.tree[u].length = t.tree[u*2+1].length + t.tree[u*2+2].length
}
}
func (t *SegmentTree) query() int {
return t.tree[0].length
}
func separateSquares(squares [][]int) float64 {
n := len(squares)
events := make([][]int, 0, 2*n)
xs := make([]int, 0)
recX := make(map[int]bool)
for i := 0; i < n; i++ {
x1, y1, l := squares[i][0], squares[i][1], squares[i][2]
x2, y2 := x1+l, y1+l
events = append(events, []int{x1, x2, y1, 1})
events = append(events, []int{x1, x2, y2, -1})
if !recX[x1] {
recX[x1] = true
xs = append(xs, x1)
}
if !recX[x2] {
recX[x2] = true
xs = append(xs, x2)
}
}
slices.Sort(xs)
slices.SortFunc(events, func(a, b []int) int {
return a[2] - b[2]
})
st := newTree(xs)
area, y0 := 0.0, 0
posX := make(map[int]int)
for i, val := range xs {
posX[val] = i
}
for _, event := range events {
x1, x2, y, k := event[0], event[1], event[2], event[3]
width := st.query()
area += float64((y - y0) * width)
st.modify(0, posX[x1], posX[x2]-1, k)
y0 = y
}
target := area / 2.0
area = 0.0
for _, event := range events {
x1, x2, y, k := event[0], event[1], event[2], event[3]
width := st.query()
area += float64((y - y0) * width)
st.modify(0, posX[x1], posX[x2]-1, k)
if area >= target {
return float64(y) - (area-target)/float64(width)
}
y0 = y
}
return 0.0
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 203.121.235.241 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1768397599.A.FD2.html
討論串 (同標題文章)
完整討論串 (本文為第 1563 之 1563 篇)：