云计算开发，2019.4.5

1. 0/1 String

package main

import (
    "fmt"
    "strings"
)

func main() {
    var n int
    var s string
    fmt.Scanln(&n)
    fmt.Scanln(&s)
    bitsOf1 := strings.Count(s, "1")
    bitsOf0 := n - bitsOf1
    if bitsOf1 >= bitsOf0 {
        fmt.Println(bitsOf1 - bitsOf0)
    } else {
        fmt.Println(bitsOf0 - bitsOf1)
    }
}

------
10
1001000101

2

Process finished with exit code 0

2. 零钱组合

package main

import (
    "fmt"
    "sort"
)

func main() {
    var m, n int
    fmt.Scanf("%d %d", &m, &n)
    coinValues := make([]int, n)
    for i := 0; i < n; i++ {
        fmt.Scanln(&coinValues[i])
    }

    sort.Slice(coinValues, func(i, j int) bool {
        return coinValues[i] > coinValues[j]
    })
    fmt.Println(minCoins(m, n, coinValues))
}

func minCoins(target, n int, coinValues []int) int {
    if coinValues[n-1] != 1 { // 若没有 1 元硬币，则此题无解
        return -1
    }
    coinNum := 0  // 当前硬币总数
    maxValue := 0 // 当前硬币总金额

    coinNums := make([]int, target+1) // 记录每个硬币的数量
    coinNums[0] = 0

    for i := 1; i <= target; i++ {
        if i > maxValue { // 目标金额比 maxValue 大
            for _, coinValue := range coinValues {
                if i >= coinValue { // 取可凑成该金额的最大硬币
                    coinNum++
                    maxValue += coinValue
                    break
                }
            }
            coinNums[i] = coinNum
        } else {
            coinNums[i] = coinNums[i-1]
        }
    }
    return coinNums[target]
}

------
20 4
1
5
2
10

5

Process finished with exit code 0

3. 怪兽过关

package main

import "fmt"

func main() {
    var n int // 怪兽数量
    fmt.Scanln(&n)
    boss := make([]int, n)
    coins := make([]int, n)
    for i := 0; i < n; i++ {
        fmt.Scan(&boss[i])
    }
    for i := 0; i < n; i++ {
        fmt.Scan(&coins[i])
    }

    curValue := boss[0]
    curCoins := coins[0]

    fmt.Println(challenge(boss, coins, 1, n, curValue, curCoins))
}

func challenge(boss []int, coins []int, curIndex, n int, curValue, curCoins int) int {
    if curIndex == n {
        return curCoins
    }
    if boss[curIndex] > curValue {
        return challenge(boss, coins, curIndex+1, n, curValue+boss[curIndex], curCoins+coins[curIndex])
    } else {
        return min(challenge(boss, coins, curIndex+1, n, curValue, curCoins), challenge(boss, coins, curIndex+1, n, curValue+boss[curIndex], curCoins+coins[curIndex]))
    }
}

func min(a, b int) int {
    if a < b {
        return a
    } else {
        return b
    }
}

------
5
8 1 1 10 13
2 1 1 3 4

5

Process finished with exit code 0