2021-12-17：长城守卫军问题。 长城上有连成一排的n个烽火台，每个烽火台都有士兵驻守。 第i个烽火台驻守着ai个士兵，相邻峰火台的距离为1。另外，有m位将军， 每位将军可以驻守一个峰火台，每个烽火台可以有多个将军驻守， 将军可以影响所有距离他驻守的峰火台小于等于x的烽火台。 每个烽火台的基础战斗力为士兵数，另外，每个能影响此烽火台的将军都能使这个烽火台的战斗力提升k。 长城的战斗力为所有烽火台的战斗力的最小值。 请问长城的最大战斗力可以是多少？ 输入描述 第一行四个正整数n,m,x,k(1<=x<=n<=10^5,0<=m<=10^5,1<=k<=10^5) 第二行n个整数ai(0<=ai<=10^5) 输出描述 仅一行，一个整数，表示长城的最大战斗力 样例输入 5 2 1 2 4 4 2 4 4 样例输出 6 来自360。

答案2021-12-17：

这道题很难。 从业务里找限制。 1.二分答案。 2.类似于AOE贪心。 3.线段树。 时间复杂度：未知。 空间复杂度：未知。

代码用golang编写。代码如下：

package main

import "fmt"

func main() {
	wall := []int{3, 1, 1, 1, 3}
	m := 2
	x := 3
	k := 1
	fmt.Println(maxForce(wall, m, x, k))
}

func maxForce(wall []int, m, x, k int) int {
	L := 0
	R := 0
	for _, num := range wall {
		if num > R {
			R = num
		}
	}
	R += m * k
	ans := 0
	for L <= R {
		M := (L + R) / 2
		if can(wall, m, x, k, M) {
			ans = M
			L = M + 1
		} else {
			R = M - 1
		}
	}
	return ans
}

func can(wall []int, m, x, k, limit int) bool {
	N := len(wall)
	// 注意：下标从1开始
	st := NewSegmentTree(wall)
	st.build(1, N, 1)
	need := 0
	for i := 0; i < N; i++ {
		// 注意：下标从1开始
		cur := st.query(i+1, i+1, 1, N, 1)
		if cur < limit {
			add := (limit - cur + k - 1) / k
			need += add
			if need > m {
				return false
			}
			st.add(i+1, getMin(i+x, N), add*k, 1, N, 1)
		}
	}
	return true
}

func getMin(a, b int) int {
	if a < b {
		return a
	} else {
		return b
	}
}

type SegmentTree struct {
	MAXN    int
	arr     []int
	sum     []int
	lazy    []int
	change  []int
	update0 []bool
}

func NewSegmentTree(origin []int) *SegmentTree {
	ret := &SegmentTree{}
	ret.MAXN = len(origin) + 1
	ret.arr = make([]int, ret.MAXN)
	for i := 1; i < ret.MAXN; i++ {
		ret.arr[i] = origin[i-1]
	}
	ret.sum = make([]int, ret.MAXN<<2)
	ret.lazy = make([]int, ret.MAXN<<2)
	ret.change = make([]int, ret.MAXN<<2)
	ret.update0 = make([]bool, ret.MAXN<<2)
	return ret
}

func (this *SegmentTree) pushUp(rt int) {
	this.sum[rt] = this.sum[rt<<1] + this.sum[rt<<1|1]
}

func (this *SegmentTree) pushDown(rt, ln, rn int) {
	if this.update0[rt] {
		this.update0[rt<<1] = true
		this.update0[rt<<1|1] = true
		this.change[rt<<1] = this.change[rt]
		this.change[rt<<1|1] = this.change[rt]
		this.lazy[rt<<1] = 0
		this.lazy[rt<<1|1] = 0
		this.sum[rt<<1] = this.change[rt] * ln
		this.sum[rt<<1|1] = this.change[rt] * rn
		this.update0[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
	}
}

func (this *SegmentTree) build(l, r, 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, R, C, l, r, rt int) {
	if L <= l && r <= R {
		this.update0[rt] = true
		this.change[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)
}

func (this *SegmentTree) add(L, R, C, l, r, rt int) {
	if L <= l && r <= R {
		this.sum[rt] += C * (r - l + 1)
		this.lazy[rt] += C
		return
	}
	mid := (l + r) >> 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)
	}
	this.pushUp(rt)
}

func (this *SegmentTree) query(L, R, l, r, 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代码