pdd 笔试

第三题（从中餐和晚餐中分别选一顿（包含热量+美味）或不选），求满足美味 >=t 的最小热量

// 排序（两个都升序：美味） + 二分（中午选一餐，二分晚餐，特别处理两者都不选以及不选中餐的情况）
// 当然，中餐降序，晚餐升序，双指针（指向中餐和晚餐）效率更高
package main

import (
    "fmt"
    "sort"
)

type node struct {
    h, d int
}

const maxn = 100005
const maxm = 100005

func main() {
    middum , evening := [maxn]node{}, [maxm]node{}
    var n, m, t int
    fmt.Scan(&n, &m, &t)
    for i := 0; i < n; i++ {
        cur := node{}
        fmt.Scan(&cur.h, &cur.d)
        middum[i] = cur
    }
    for i := 0; i < m; i++ {
        cur := node{}
        fmt.Scan(&cur.h, &cur.d)
        evening[i] = cur
    }

    if t == 0 { // 不要美味自然无需热量
        fmt.Println("0")
        return
    }
    getSorted(middum[:n])
    getSorted(evening[:m])
    if middum[n-1].d + evening[m-1].d < t { // 中餐+晚餐最大美味都达不到指定阈值
        fmt.Println("-1")
        return
    }

    ans := 200005
    for k := m-1; k >= 0; k-- { // 只选晚餐，确保美味满足阈值时热量最小即可
        if evening[k].d < t {
            break
        }
        ans = evening[k].h
    }
    for i := 0; i < n; i++ {
        cur := middum[i].h
     // 这里用 t > middum[i].d 是错误的，考试犯了这个巨大错误，导致只拿到30%分数！！！
        if middum[i].d + evening[m-1].d >= t { 
            cur += minH(evening[:m], t-middum[i].d)
        }
        ans = min(ans, cur)
    }
    fmt.Println(ans)
}

func minH(evening []node, d int) int {
    lo, hi := 0, len(evening)-1

    for lo < hi {
        mid := (lo+hi)/2
        if evening[mid].d >= d {
            hi = mid
        } else {
            lo = mid+1
        }
    }

    return evening[hi].h
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func getSorted(cur []node) {
    sort.Slice(cur, func(i, j int) bool {
        if (cur[i].d < cur[j].d) || (cur[i].d == cur[j].d && cur[i].h < cur[j].h) {
            return true
        }
        return false
    })
}