F - Vouchers

[hxrxchang]

https://atcoder.jp/contests/abc308/tasks/abc308_f

問題概要

N個の商品の定価が分かっている。 M枚クーポンがあり、クーポンは定価がL円以上の商品に対してD円安くなるというものである。 クーポンは1枚につき1回までしか使えない、また同じ商品に複数クーポンは使えない。 N個のすべての商品を買うのに必要な最小金額を求めよ。

解き方

割引額が大きいクーポンから順に貪欲に使っていけばいい。 各クーポンが使えるかどうかは商品の定価から二分探索で、クーポンが使える条件の金額と商品の定価が最も近いものを選べばいい。

func solve() {
    in := getInts()
    m := in[1]

    p := getInts()
    l := getInts()
    d := getInts()

    coupons := make([]Coupon, m)
    for i := 0; i < m; i++ {
        coupons[i] = Coupon{l[i], d[i]}
    }
    sort.Slice(coupons, func(i, j int) bool {
        return coupons[i].d > coupons[j].d
    })

    ss := newSortedSet[int]()
    sCnt := make(map[int]int)
    for _, v := range p {
        ss.add(v)
        sCnt[v]++
    }

    ans := 0
    for _, coupon := range coupons {
        item := ss.lowerBound(coupon.l)
        if item.IsValid() {
            ans += item.Value() - coupon.d
            sCnt[item.Value()]--
            if sCnt[item.Value()] == 0 {
                ss.remove(item.Value())
            }
        }
    }

    for _, v := range maps.Keys(sCnt) {
        ans += v * sCnt[v]
    }

    fmt.Println(ans)
}

https://atcoder.jp/contests/abc308/submissions/56677532