2021-11-19：[0,4,7] ： 0表示这里石头没有颜色，如果变红代

原创

福大大架构师每日一题

发布于 2022-11-20 23:10:09

2160

发布于 2022-11-20 23:10:09

2021-11-19：0,4,7 ： 0表示这里石头没有颜色，如果变红代价是4，如果变蓝代价是7，1,X,X ： 1表示这里石头已经是红，而且不能改颜色，所以后两个数X无意义，2,X,X ： 2表示这里石头已经是蓝，而且不能改颜色，所以后两个数X无意义，颜色只可能是0、1、2，代价一定>=0，给你一批这样的小数组，要求最后必须所有石头都有颜色，且红色和蓝色一样多，返回最小代价。如果怎么都无法做到所有石头都有颜色、且红色和蓝色一样多，返回-1。来自小红书。

答案2021-11-19：

1.排序。具体见代码。

2.统计无色，红色，蓝色个数。

3.如果红色或者蓝色过半，直接返回-1。

4.遍历，计算最小代价。具体见代码。

时间复杂度：排序的。

空间复杂度：排序的。

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

package main

import (
    "fmt"
    "sort"
)

func main() {
    stones := [][]int{{0, 2, 4}, {0, 4, 1}}
    ret := minCost(stones)
    fmt.Println(ret)
}

func minCost(stones [][]int) int {
    n := len(stones)
    if (n & 1) != 0 {
        return -1
    }
    sort.Slice(stones, func(i, j int) bool {
        a := stones[i]
        b := stones[j]
        if a[0] == 0 && b[0] == 0 {
            return b[1]-b[2]-a[1]+a[2] < 0
        } else {
            return a[0]-b[0] < 0
        }
    })
    zero := 0
    red := 0
    blue := 0
    cost := 0
    for i := 0; i < n; i++ {
        if stones[i][0] == 0 {
            zero++
            cost += stones[i][1]
        } else if stones[i][0] == 1 {
            red++
        } else {
            blue++
        }
    }
    if red > (n>>1) || blue > (n>>1) {
        return -1
    }
    blue = zero - ((n >> 1) - red)
    for i := 0; i < blue; i++ {
        cost += stones[i][2] - stones[i][1]
    }
    return cost
}

执行结果如下：