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
}
执行结果如下：
左神java代码
![2023-05-02：如果一个正整数每一个数位都是 互不相同 的，我们称它是 特殊整数 。 给你一个正整数 n ，请你返回区间 [1, n] 之间特殊整数的数目。 输入：n = 20。 输出：19。](https://www.kunjuke.com/file/css/thumb/8.jpg/280-180.jpg)
![2023-04-13：给定一个字符串数组strs，其中每个字符串都是小写字母组成的， 如果i ＜ j，并且strs[i]和strs[j]所有的字符随意去排列能组成回文串， 那么说(i,j)叫做一个互补](https://www.kunjuke.com/file/css/thumb/2.jpg/280-180.jpg)
![2022-08-18:每一个序列都是[a,b]的形式，a ＜ b 序列连接的方式为，前一个序列的b，要等于后一个序列的a 比如 : [3, 7]、[7, 13]、[13, 26]这三个序列就可以依次连](https://www.kunjuke.com/file/css/thumb/6.jpg/280-180.jpg)
![2022-01-12：给定一个正数数组arr，长度为n，下标0~n-1， arr中的0、n-1位置不需要达标，它们分别是最左、最右的位置， 中间位置i需要达标，达标的条件是 : arr[i-1] ＞](https://www.kunjuke.com/file/css/thumb/4.jpg/280-180.jpg)
![2021-04-22：给定很多线段，每个线段都有两个数[start, end]，表示线段开始位置和结束位置，左右都是闭区间，规定：1）线段的开始和结束位置一定都是整数值，2）线段重合区域的长度必须＞=](https://www.kunjuke.com/file/css/thumb/11.jpg/280-180.jpg)
![2022-08-20：给定区间的范围[xi,yi]，xi＜=yi，且都是正整数， 找出一个坐标集合set，set中有若干个数字， set要和每个给定的区间，有交集。 求set的最少需要几个数。 比如给](https://www.kunjuke.com/file/css/thumb/10.jpg/280-180.jpg)