[leetcode 2528][Go][二分答案][差分数组][前缀和]最大化城市的最小电量

题目链接

leetcode 2528 最大化城市的最小电量

解题思路

二分查找

首先最大问题最小化第一个先尝试使用二分查找，那就把大问题转化成了小问题:设一个值low，能否在新建供电站数量小于等于k的情况下使城市电量的最小值大于等于low。 然后对low进行二分查找即可。

1
2
3
4
5
6
7
8
9
10
11
func maxPower(stations []int, r int, k int) int64 {
    //预处理TODO
    //minP为所有城市初始电量的最小值
    //power[i]表示第i个城市的初始电量
    //sub为子问题

	ret := sort.Search(k+1, func(i int) bool {
		return !sub(i+minP, r, k, power) 
	}) - 1 + minP
	return int64(ret)
}

二分查找复杂度为

预处理每个城市的初始电量(前缀和)

每个城市的初始电量即当前城市左右范围r内的电站数量和，那么就可以求出电站数量的前缀和sum[]，再求出每个城市的初始电量power[]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var n = len(stations)
var sum = make([]int, n)
var power = make([]int, n)
for i := range n {
    if i > 0 {
        sum[i] += sum[i-1]
    }
    sum[i] += stations[i]
}
for i := range n {
    if i-r-1 >= 0 {
        power[i] = sum[min(n-1, i+r)] - sum[i-r-1]
    } else {
        power[i] = sum[min(n-1, i+r)]
    }
}

以上代码求电站数量时间复杂度为

子问题处理(贪心+差分数组)

添加电站后组要对范围内的电量进行修改，连续范围的修改就可以用差分数组diff实现。设i为当前城市下标，那么此时i以前的城市电量应该都大于等于low，所以为了最大化利用电站城市i应该在电站范围的最左边，即新建电站n满足n-r == i，那么新建电站的影响范围即为[i, i+2*r]。根据差分数组的性质，设d = low - power[i] (low > power[i])，那么就应该对diff[i]加d，对diff[i+2*r+1]减d。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func sub(low int, r int, k int, power []int) bool {
	var n = len(power)
	var diff = make([]int, n)
	for i := range n {
		if i > 0 {
			diff[i] = power[i] - power[i-1]
		} else {
			diff[i] = power[i]
		}
	}
	sum := 0 //用于记录电站当前电量
	for i := range n {
		sum += diff[i]
		if sum < low {
			d := low - sum
			if i+2*r+1 < n {
				diff[i+2*r+1] -= d
			}
			diff[i] += d //可有可无，diff[i]不会再被读取
			sum += d
			k -= d //减少剩余可用电站
			if k < 0 {
				return false
			}
		}
	}
	return true
}

以上差分数组初始化以及后续遍历时间复杂度都为所以子问题时间复杂度为

时间复杂度

以上代码总时间复杂度为

全部代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
func sub(low int, r int, k int, power []int) bool {
	var n = len(power)
	var diff = make([]int, n)
	for i := range n {
		if i > 0 {
			diff[i] = power[i] - power[i-1]
		} else {
			diff[i] = power[i]
		}
	}
	sum := 0
	for i := range n {
		sum += diff[i]
		if sum < low {
			d := low - sum
			if i+2*r+1 < n {
				diff[i+2*r+1] -= d
			}
			diff[i] += d
			sum += d
			k -= d
			if k < 0 {
				return false
			}
		}
	}
	return true
}

func maxPower(stations []int, r int, k int) int64 {
	var n = len(stations)
	var sum = make([]int, n)
	var power = make([]int, n)
	for i := range n {
		if i > 0 {
			sum[i] += sum[i-1]
		}
		sum[i] += stations[i]
	}
	minP := math.MaxInt
	for i := range n {
		if i-r-1 >= 0 {
			power[i] = sum[min(n-1, i+r)] - sum[i-r-1]
		} else {
			power[i] = sum[min(n-1, i+r)]
		}
		minP = min(minP, power[i])
	}
	ret := sort.Search(k+1, func(i int) bool {
		return !sub(i+minP, r, k, power)
	}) - 1 + minP
	return int64(ret)
}