2021-11-19:[0,4,7]:0 means that the stone here has no color. If it turns red

2021-11-19：0,4,7 ： 0 The stone here has no color , If it turns red, the price is 4, If it turns blue, the price is 7,1,X,X ： 1 It means that the stone here is already red , And you can't change the color , So the last two numbers X meaningless ,2,X,X ： 2 It means that the stone here is already blue , And you can't change the color , So the last two numbers X meaningless , The color can only be 0、1、2, The price must be >=0, Give you a batch of such small arrays , Finally, all stones must have color , And there are as many red and blue , Returns the minimum cost . If you can't do it anyway, all stones have color 、 And there are as many red and blue , return -1. From little red book .

answer 2021-11-19：

1. Sort . See code for details .

2. Statistics are colorless , Red , Number of blue .

3. If red or blue is more than half , Go straight back to -1.

4. Traverse , Calculate the minimum cost . See code for details .

Time complexity ： Sort of .

Spatial complexity ： Sort of .

The code to use golang To write . The code is as follows ：

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
}

The results are as follows ：

picture

Zuo Shen java Code