贪心法的概念：遵循某个规则，不断贪心地选取当前最优策略的算法设计方法。
硬币问题凭直觉，可以得到一个规则，尽可能地多用面值大的硬币。
硬币问题是贪心算法中较为简单的例子。在搜索算法和动态规则算法是在多种策略中选取最优解；而贪心算法它是遵循某种规则，不断地选取当前最优策略。
package main
import "fmt"
var coin = []int{1, 5, 10, 50, 100, 500}
var coins = [6]int{}
var A int
func solve() {
ans := 0
for i := 5; i >= 0; i-- {
t := min(A/coin[i], coins[i])
A -= t * coins[i]
ans++
}
fmt.Println(ans)
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func main() {
fmt.Scanf("%d %d %d %d %d %d", &coins[0], &coins[1], &coins[2], &coins[3], &coins[4], &A)
solve()
}
区间问题
这个问题不像前面的硬币问题那么简单。最容易想到的一种贪心算法如下：
在可选的工作中，每次都选取开始时间最早的工作。但这种情况对于下列情况无法得到正确的答案。
除此之外，还会想到其他的想法：
（1）在可选的工作中，每次都选取结束时间最早的工作
（2）在可选的工作中，每次都选取用时最短的工作
（3）在可选的工作中，每次都选取与最少可选工作有重叠的工作**（我觉得这个想不到）**
对结束时间排序，然后选取完任务后记录结束时间，寻找下一个开始时间比记录的结束时间要晚的任务。
package main
import (
"fmt"
"sort"
)
const N = 100000
var s = [N]int{}
var t = [N]int{}
type itv struct{ x, y int }
var itvs = make([]itv, N)
func solve() {
for i := 0; i < N; i++ {
itvs[i].x = t[i]
itvs[i].y = s[i]
}
sort.Slice(itvs, func(i, j int) bool { return itvs[i].x < itvs[j].x })
ans, t := 0, 0
for i := 0; i < N; i++ {
if t < itvs[i].y {
t = itvs[i].x
ans++
}
}
fmt.Println(ans)
}
func main() {
s = [N]int{1, 2, 4, 6, 8}
t = [N]int{3, 5, 7, 9, 10}
solve()
}
字典序最小问题
字典序：从前到后比较两个字符串大小的方法。
可以很容易的想到：不断取 S S S开头和末尾中较小的一个字符放到 T T T的末尾
但是，如果开头和末尾的字母相同怎么办？
从开头和末尾往中间找，找到第一个不同的。假设左边第一个不同的字典序最小，则取左边的，否则取右边的。
package main
import "fmt"
var N int
var s = []byte{}
func solve() {
a, b := 0, N-1
t := []byte{}
for a <= b {
left := false
for i := 0; a+i < b; i++ {
if s[a+i] < s[b] {
left = true
break
} else if s[a+i] > s[b] {
left = false
break
}
}
if left {
t = append(t, s[a])
a++
} else {
t = append(t, s[b])
b--
}
}
fmt.Println(string(t))
}
func main() {
N = 6
s = []byte{'A', 'C', 'D', 'B', 'C', 'B'}
solve()
}
2.2.4 其他例题
**做题思路：**从第一个点距离R的最远点做标记，如此重复
package main
import "sort"
var N, R int
var X = []int{}
func solve() {
sort.Ints(X)
start, ans := 0, 0
for start < N {
s := X[start]
start++
// 标记点的左边
for start < N && X[start] <= s+R {
start++
}
// 标记点的右边
p := X[start-1]
for start < N && X[start] <= p+R {
start++
}
ans++
}
println(ans)
}
func main() {
N = 6
R = 10
X = []int{1, 7, 15, 20, 30, 50}
solve()
}
例题二：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Pa9J0Gir-1648387773733)(%E4%B8%80%E5%BE%80%E7%9B%B4%E5%89%8D%EF%BC%81%E8%B4%AA%E5%BF%83%E6%B3%95%20def84/Untitled%209.png)]
做题思路：
每一次切割，得到的结果必然是两块。而且，木板总是越切越短的。因此，我们可以结合二叉树来解题（如下图）。
叶子节点的深度就对应了木板所需切割次数，开销的合计就是各个叶子节点的总和。因为一块木板一直在以叶子节点的长度为结果在切割。
所以开销公式为：木板的长度 × times ×节点的深度
所以，不难推导出贪心算法的规则，最短的木板总是在最深处的。所以我们可以对切成的木板的长度从小到大进行排序。然后每两块为一个节点。
( L 1 + L 2 ) , L 3 , L 4 , ⋯ , L N (L_1+L_2),L_3,L_4,cdots,L_N (L1+L2),L3,L4,⋯,LN
也就是说，每次找到最短和次短的木板，求和。
package main
var N int
var L = []int{}
func solve() {
ans := 0
for N > 1 {
min1, min2 := 0, 1
if L[min1] > L[min2] {
L[min1], L[min2] = L[min2], L[min1]
}
for i := 2; i < N; i++ {
if L[i] < L[min1] {
min2 = min1
min1 = i
} else if L[i] < L[min2] {
min2 = i
}
}
t := L[min1] + L[min2]
L[min1], L[min2] = t, L[N-1]
ans += t
N--
}
println(ans)
}
func main() {
N = 3
L = []int{8, 5, 8}
solve()
}
