挑战程序设计竞赛2 算法与数据结构5.6

5.6 搜索的应用----计算最优解

package main

import (
    "fmt"
    "os"
)
var n, k int
var MAX = 100000
var T = make([]int64, MAX)

//k辆车最大能运载为P的卡车能装多少货物
func check(P int64) int {
    var i int
    for j := 0; j < k; j++ {
        var s int64
        for s+T[i] <= P {
            s += T[i]
            i++
            if i == n {
                return n
            }
        }
    }
    return i
}
func solve() int64 {
    var left, right, mid int64 = 0, 100000*10000, 0

    for right-left > 1 {
        mid = (left + right) / 2
        v := check(mid)
        if v >= n {
            right = mid
        } else {
            left = mid
        }
    }
    return right
}
//初始化程序，设置从文件读取
func init()  {
    out, _ := os.OpenFile("./challenge/5_6.out", os.O_WRONLY|os.O_CREATE,0755)
    fin, _ := os.OpenFile("./challenge/5_6.in", os.O_RDONLY,0755)
    os.Stdout = out
    os.Stderr = out
    os.Stdin=fin
}
func main() {
    fmt.Scanf("%d %d", &n, &k)
    for i := 0; i < n; i++ {
        fmt.Scanf("%d", &T[i])
    }
    ans := solve()
    fmt.Println(ans)
}