技巧
优先队列 贪心
思路
这里存在两个维度 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) }