给定一个正数数组arr长度为n、正数x、正数y。
你的目标是让arr整体的累加和<=0，
你可以对数组中的数num执行以下三种操作中的一种，且每个数最多能执行一次操作 :
1.不变；
2.可以选择让num变成0，承担x的代价；
3.可以选择让num变成-num，承担y的代价。
返回你达到目标的最小代价。
数据规模 : 面试时面试官没有说数据规模。
贪心。从大到小排序。
x>=y时，就只执行y操作，没有x操作。
x<y时，先执行y操作，再执行x操作，最后无操作。这三种操作不可能交替。
时间复杂度：排序的。
空间复杂度：排序的。
代码用golang编写。代码如下：
package main
import (
"fmt"
"sort"
)
func main() {
arr := []int{1, 2, 3, 4, 5}
ret := minOpStep3(arr, 4, 3)
fmt.Println(ret)
}
func minOpStep3(arr []int, x, y int) int {
// 系统排序，小 -> 大
sort.Ints(arr)
n := len(arr)
// 如何变成 大 -> 小
for l, r := 0, n-1; l <= r; l, r = l+1, r-1 {
tmp := arr[l]
arr[l] = arr[r]
arr[r] = tmp
}
if x >= y {
sum := 0
for _, num := range arr {
sum += num
}
cost := 0
for i := 0; i < n && sum > 0; i++ {
sum -= arr[i] << 1
cost += y
}
return cost
} else {
// 0个数执行Y
benefit := 0
// 全部的数都需要执行x，才能让累加和<=0
cost := len(arr) * x
holdSum := 0
for yRight, holdLeft := 0, n; yRight < holdLeft-1; yRight++ {
benefit += arr[yRight]
for holdLeft-1 > yRight && holdSum+arr[holdLeft-1] <= benefit {
holdSum += arr[holdLeft-1]
holdLeft--
}
// 0...yRight x holdLeft....
cost = getMin(cost, (yRight+1)*y+(holdLeft-yRight-1)*x)
}
return cost
}
}
func getMin(a, b int) int {
if a < b {
return a
} else {
return b
}
}执行结果如下：
