长城守卫军问题。
长城上有连成一排的n个烽火台，每个烽火台都有士兵驻守。
第i个烽火台驻守着ai个士兵，相邻峰火台的距离为1。另外，有m位将军，
每位将军可以驻守一个峰火台，每个烽火台可以有多个将军驻守，
将军可以影响所有距离他驻守的峰火台小于等于x的烽火台。
每个烽火台的基础战斗力为士兵数，另外，每个能影响此烽火台的将军都能使这个烽火台的战斗力提升k。
长城的战斗力为所有烽火台的战斗力的最小值。
请问长城的最大战斗力可以是多少？
输入描述
第一行四个正整数n,m,x,k(1<=x<=n<=105,0<=m<=105,1<=k<=10^5)
第二行n个整数ai(0<=ai<=10^5)
输出描述 仅一行，一个整数，表示长城的最大战斗力
样例输入
5 2 1 2
4 4 2 4 4
样例输出
6
这道题很难。
从业务里找限制。
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
}执行结果如下：
