技巧
优先队列 贪心
思路
这里存在两个维度 t1: 修理需要花费的时间 t2: deadline
按照截止时间升序排列
然后依次按照顺序遍历每个任务, 遵循能修则修,不能修的话就和已经修的比一下看看是不是比之前修过的划算。要是划算就替换。
实现
package main
import (
"bufio"
. "fmt"
"io"
"os"
"sort"
)
type Building struct {
T1, T2 int
}
func siftDown(heap []int, last int) {
curr := 0
for curr < last {
max := curr
li,ri := 2*curr+1, 2*curr+2
if li < last {
if heap[li] > heap[max] {
max = li
}
if ri < last && heap[ri] > heap[max] {
max = ri
}
}
if max == curr {
break
}
heap[curr], heap[max] = heap[max], heap[curr]
curr = max
}
}
func siftUp(h []int, i int) {
for i != 0 && h[i] > h[(i-1)/2] {
h[i], h[(i-1)/2] = h[(i-1)/2], h[i]
i = (i - 1) / 2
}
}
// https://ac.nowcoder.com/acm/problem/20154
func NC20154(_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([]Building, n)
heap, ipos := make([]int, n), 0
for i := 0; i < n; i++ {
Fscan(in, &arr[i].T1, &arr[i].T2)
}
sort.Slice(arr, func(i, j int) bool {
return arr[i].T2 <= arr[j].T2
})
t := 0
for i := 0; i < n; i++ {
if t+arr[i].T1 <= arr[i].T2 {// 能修则修
t += arr[i].T1
heap[ipos] = arr[i].T1
siftUp(heap, ipos)
ipos++
} else if heap[0] > arr[i].T1 { // 修不成,择优选择 看看能否极限一换一
t -= heap[0]
heap[0] = arr[i].T1
t += heap[0]
siftDown(heap, ipos)
}
}
Fprintln(out, ipos)
}
func main() {
NC20154(os.Stdin, os.Stdout)
}

京公网安备 11010502036488号