七叶笔记 » golang编程 » 2022-01-11：给定一个正数数组arr长度为n、正数x、正数y。 你的目

2022-01-11：给定一个正数数组arr长度为n、正数x、正数y。 你的目

分类: golang编程 | 浏览: 244

2022-01-11：给定一个正数数组arr长度为n、正数x、正数y。

你的目标是让arr整体的累加和<=0，

你可以对数组中的数num执行以下三种操作中的一种，且每个数最多能执行一次操作 :

1.不变；

2.可以选择让num变成0，承担x的代价；

3.可以选择让num变成-num，承担y的代价。

返回你达到目标的最小代价。

数据规模 : 面试时面试官没有说数据规模。

来自微软面试。

答案2022-01-11：

贪心。从大到小排序。

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
    }
}

执行结果如下：

***

[左神java代码](

相关文章