2021-05-08：给定两个非负数组x和hp，长度都是N，再给定一个正数range。x有序，x[i]表示i号怪兽在x轴上的位置；hp[i]表示i号怪兽的血量 。range表示法师如果站在x位置，用AOE技能打到的范围是： [x-range,x+range]，被打到的每只怪兽损失1点血量 。返回要把所有怪兽血量清空，至少需要释放多少次AOE技能？
福大大 答案2021-05-08：
1.贪心策略：永远让最左边缘以最优的方式(AOE尽可能往右扩，最让最左边缘盖住目前怪的最左)变成0，也就是选择：一定能覆盖到最左边缘, 但是尽量靠右的中心点。等到最左边缘变成0之后，再去找下一个最左边缘…
2.贪心策略加线段树，可优化成O(N * logN)的方法。
代码用golang编写。代码如下：
package main
import "fmt"
func main() {
if true {
x := []int{0, 1, 2, 3, 4, 5, 6}
hp := []int{6, 4, 2, 9, 3, 6, 4}
range2 := 4
ret := minAoe1(x, hp, range2)
fmt.Println(ret)
}
if true {
x := []int{0, 1, 2, 3, 4, 5, 6}
hp := []int{6, 4, 2, 9, 3, 6, 4}
range2 := 4
ret := minAoe2(x, hp, range2)
fmt.Println(ret)
}
}
// 贪心策略：永远让最左边缘以最优的方式(AOE尽可能往右扩，最让最左边缘盖住目前怪的最左)变成0，也就是选择：
// 一定能覆盖到最左边缘, 但是尽量靠右的中心点
// 等到最左边缘变成0之后，再去找下一个最左边缘...
func minAoe1(x []int, hp []int, range2 int) int {
N := len(x)
ans := 0
for i := 0; i < N; i++ {
if hp[i] > 0 {
triggerPost := i
for triggerPost < N && x[triggerPost]-x[i] <= range2 {
triggerPost++
}
ans += hp[i]
aoe(x, hp, i, triggerPost-1, range2)
}
}
return ans
}
func aoe(x []int, hp []int, L int, trigger int, range2 int) {
N := len(x)
RPost := trigger
for RPost < N && x[RPost]-x[trigger] <= range2 {
RPost++
}
minus := hp[L]
for i := L; i < RPost; i++ {
hp[i] = getMax(0, hp[i]-minus)
}
}
func getMax(a int, b int) int {
if a > b {
return a
} else {
return b
}
}
// 贪心策略和方法二一样，但是需要用线段树，可优化成O(N * logN)的方法，
func minAoe2(x []int, hp []int, range2 int) int {
N := len(x)
// coverLeft[i]：如果以i为中心点放技能，左侧能影响到哪，下标从1开始，不从0开始
// coverRight[i]：如果以i为中心点放技能，右侧能影响到哪，下标从1开始，不从0开始
coverLeft := make([]int, N+1)
coverRight := make([]int, N+1)
left := 0
right := 0
for i := 0; i < N; i++ {
for x[i]-x[left] > range2 {
left++
}
for right < N && x[right]-x[i] <= range2 {
right++
}
coverLeft[i+1] = left + 1
coverRight[i+1] = right
}
// best[i]: 如果i是最左边缘点，选哪个点做技能中心点最好，下标从1开始，不从0开始
best := make([]int, N+1)
trigger := 0
for i := 0; i < N; i++ {
for trigger < N && x[trigger]-x[i] <= range2 {
trigger++
}
best[i+1] = trigger
}
st := NewSegmentTree(hp)
st.build(1, N, 1)
ans := 0
for i := 1; i <= N; i++ {
leftEdge := st.query(i, i, 1, N, 1)
if leftEdge > 0 {
ans += leftEdge
t := best[i]
l := coverLeft[t]
r := coverRight[t]
st.add(l, r, (int)(-leftEdge), 1, N, 1)
}
}
return ans
}
type SegmentTree struct {
// arr[]为原序列的信息从0开始，但在arr里是从1开始的
// sum[]模拟线段树维护区间和
// lazy[]为累加懒惰标记
// change[]为更新的值
// update[]为更新慵懒标记
MAXN int
arr []int
sum []int
lazy []int
change2 []int
update2 []bool
}
func NewSegmentTree(origin []int) *SegmentTree {
ret := &SegmentTree{}
MAXN := len(origin) + 1
ret.arr = make([]int, MAXN) // arr[0] 不用 从1开始使用
for i := 1; i < MAXN; i++ {
ret.arr[i] = origin[i-1]
}
ret.sum = make([]int, MAXN<<2) // 用来支持脑补概念中，某一个范围的累加和信息
ret.lazy = make([]int, MAXN<<2) // 用来支持脑补概念中，某一个范围沒有往下傳遞的纍加任務
ret.change2 = make([]int, MAXN<<2) // 用来支持脑补概念中，某一个范围有没有更新操作的任务
ret.update2 = make([]bool, MAXN<<2) // 用来支持脑补概念中，某一个范围更新任务，更新成了什么
return ret
}
func (this *SegmentTree) pushUp(rt int) {
this.sum[rt] = this.sum[rt<<1] + this.sum[rt<<1|1]
}
// 之前的，所有懒增加，和懒更新，从父范围，发给左右两个子范围
// 分发策略是什么
// ln表示左子树元素结点个数，rn表示右子树结点个数
func (this *SegmentTree) pushDown(rt int, ln int, rn int) {
if this.update2[rt] {
this.update2[rt<<1] = true
this.update2[rt<<1|1] = true
this.change2[rt<<1] = this.change2[rt]
this.change2[rt<<1|1] = this.change2[rt]
this.lazy[rt<<1] = 0
this.lazy[rt<<1|1] = 0
this.sum[rt<<1] = this.change2[rt] * ln
this.sum[(rt<<1)|1] = this.change2[rt] * rn
this.update2[rt] = false
}
if this.lazy[rt] != 0 {
this.lazy[rt<<1] += this.lazy[rt]
this.sum[rt<<1] += this.lazy[rt] * ln
this.lazy[(rt<<1)|1] += this.lazy[rt]
this.sum[(rt<<1)|1] += this.lazy[rt] * rn
this.lazy[rt] = 0
}
}
// 在初始化阶段，先把sum数组，填好
// 在arr[l~r]范围上，去build，1~N，
// rt : 这个范围在sum中的下标
func (this *SegmentTree) build(l int, r int, rt int) {
if l == r {
this.sum[rt] = this.arr[l]
return
}
mid := (l + r) >> 1
this.build(l, mid, rt<<1)
this.build(mid+1, r, rt<<1|1)
this.pushUp(rt)
}
func (this *SegmentTree) update(L int, R int, C int, l int, r int, rt int) {
if L <= l && r <= R {
this.update2[rt] = true
this.change2[rt] = C
this.sum[rt] = C * (r - l + 1)
this.lazy[rt] = 0
return
}
// 当前任务躲不掉，无法懒更新，要往下发
mid := (l + r) >> 1
this.pushDown(rt, mid-l+1, r-mid)
if L <= mid {
this.update(L, R, C, l, mid, rt<<1)
}
if R > mid {
this.update(L, R, C, mid+1, r, rt<<1|1)
}
this.pushUp(rt)
}
// L..R -> 任务范围 ,所有的值累加上C
// l,r -> 表达的范围
// rt 去哪找l，r范围上的信息
func (this *SegmentTree) add(L int, R int, C int, l int, r int, rt int) {
// 任务的范围彻底覆盖了，当前表达的范围
if L <= l && r <= R {
this.sum[rt] += C * (r - l + 1)
this.lazy[rt] += C
return
}
// 任务并没有把l...r全包住
// 要把当前任务往下发
// 任务 L, R 没有把本身表达范围 l,r 彻底包住
mid := (l + r) >> 1 // l..mid (rt << 1) mid+1...r(rt << 1 | 1)
// 下发之前所有攒的懒任务
this.pushDown(rt, mid-l+1, r-mid)
// 左孩子是否需要接到任务
if L <= mid {
this.add(L, R, C, l, mid, rt<<1)
}
// 右孩子是否需要接到任务
if R > mid {
this.add(L, R, C, mid+1, r, rt<<1|1)
}
// 左右孩子做完任务后，我更新我的sum信息
this.pushUp(rt)
}
// 1~6 累加和是多少？ 1~8 rt
func (this *SegmentTree) query(L int, R int, l int, r int, rt int) int {
if L <= l && r <= R {
return this.sum[rt]
}
mid := (l + r) >> 1
this.pushDown(rt, mid-l+1, r-mid)
ans := 0
if L <= mid {
ans += this.query(L, R, l, mid, rt<<1)
}
if R > mid {
ans += this.query(L, R, mid+1, r, rt<<1|1)
}
return ans
}
执行结果如下：