题解 | #tokitsukaze and Soldier#
tokitsukaze and Soldier
https://ac.nowcoder.com/acm/problem/50439
技巧
贪心 堆
思路
本质上是将问题转换为单维度贪心（即不要去影响前面的决定）
这个题目存在两个维度 1 攻击力 2 容忍度 按照前面的说法，选人可能会影响到前面已经做了的决定，所以暂时行不通。
这里需要把问题换个角度思考 => 如何固定或者说相对固定一个维度呢？
我们先将容忍度s 按照降序处理。 然后另外再开一个容器用于收集当前已经选定的士兵
这么做的好处是将整个容忍度模型转化成了一个一次函数 ===》 \ 而且随着时间的推移我们能够知道收集容器的容量应该会越来越少
很显然，用堆结构来定义这个容器很合适 （战斗力维度组成的小根堆， 方便看情况舍弃或保留元素）
然后不断去更新堆结构找出最大值即可
这种做法也有说法叫做“可以后悔的贪心” 即在后续的决定中改变到了前面的决定。 不过整个流程中所有过程的值都被合理准确的记录下了。
实现
package main
import (
"bufio"
. "fmt"
"io"
"os"
"sort"
)
type Soldier struct {
v, s int
}
func siftDown(heap []Soldier, last int) {
curr := 0
for curr < last {
min := curr
if 2 * curr + 1 < last {
if heap[2 * curr + 1].v < heap[min].v {
min = 2 * curr + 1
}
if 2 * curr + 2 < last && heap[2 * curr + 2].v < heap[min].v {
min = 2 * curr + 2
}
}
if min == curr {
break
}
heap[curr], heap[min] = heap[min], heap[curr]
curr = min
}
}
func siftUp(heap []Soldier, i int) {
for i != 0 && heap[i].v < heap[(i-1) / 2].v {
heap[i], heap[(i-1) / 2] = heap[(i-1) / 2], heap[i]
i = (i-1) / 2
}
}
// https://ac.nowcoder.com/acm/problem/50439
func NC50439(_r io.Reader, _w io.Writer) {
in, out := bufio.NewReader(_r), bufio.NewWriter(_w)
defer out.Flush()
var n int
Fscan(in, &n)
arr := make([]Soldier, n)
for i := 0; i < n; i++ {
Fscan(in, &arr[i].v, &arr[i].s)
}
// 按照s降序排列
sort.Slice(arr, func(i, j int) bool {
if arr[i].s > arr[j].s {
return true
}else if arr[i].s == arr[j].s && arr[i].v > arr[j].v {
return true
}
return false
})
heap, last := make([]Soldier, arr[0].s), 1
ans, total := arr[0].v, arr[0].v
heap[0] = arr[0]
for i := 1; i < n; i++ {
for last >= arr[i].s && heap[0].v < arr[i].v{
total -= heap[0].v
heap[0] = heap[last - 1]
siftDown(heap, last)
last --
}
if last < arr[i].s {
heap[last] = arr[i]
total += heap[last].v
siftUp(heap, last)
last ++
}
if total > ans {
ans = total
}
}
Fprintln(out, ans)
}
func main() {
NC50439(os.Stdin, os.Stdout)
}
查看3道真题和解析