---
title: "Educational Codeforces Round 125 (Div. 2) D(枚舉+貪心+二分)"
tags: 題解, 枚舉, 貪心, 二分
---

https://codeforces.com/contest/1657/problem/D

#### 題意

有 $n$ 種軍隊，第 $i$ 種軍隊的單位成本為 $c_i$，傷害為 $d_i$，生命值為 $h_i$。

有 $m$ 隻怪物，第 $j$ 隻怪物的傷害為 $D_j$，生命值為 $H_j$。

組成軍隊的方式是選擇**一種**軍隊並招募一些 (假設為 $k$)單位，成本為 $k*c$，傷害為 $d*c$，生命值仍為 $h$。與第 $j$ 隻怪物戰鬥時，需在比怪物更短的時間殺掉怪物。成本不能大於 $C$。

問：對於每種怪物，最少需要多少成本才能戰勝，若不能戰勝則為 $-1$。

#### 思路

對於第 $i$ 種軍隊，要戰勝第 $j$ 種怪物須滿足：
$\frac{H_j}{d_i*k}<\frac{h_i}{D_j}$

可以看出我們只在乎 $d_ih_ik$ 的大小，因此我們可以針對不同成本 $c$，試著用不同種軍隊構造出最大的 $DH[c]$。對於成本 $c_2$，當 $c_1$ 可整除 $c_2$ 時（$c_2=c_1*k$），可以用 $DH[c] * k$ 去更新 $DH[c_2]$。

由於成本越大，能構造出的 $DH[c]$ 也會越大，對於怪物 $d_jh_j$，可以用二分搜索找出大於 $d_jh_j$ 中最小成本的方案，若找不到則為不可能戰勝。

#### Code

def solve():
    n, C = map(int, input().split())
 
    DH = [0 for _ in range(C + 1)]
    for _ in range(n):
        c, d, h = map(int, input().split())
        DH[c] = max(DH[c], d * h)
 
    for c in range(1, C + 1):
        DH[c] = max(DH[c], DH[c - 1])
        for c2 in range(c, C + 1, c):
            DH[c2] = max(DH[c2], DH[c] * (c2 // c))
 
    m = int(input())
 
    ans = []
    for _ in range(m):
        d, h = map(int, input().split())
        pos = bisect_right(DH, d * h)
        ans.append(pos if pos < len(DH) else -1)
 
    print(*ans)
 
if __name__ == "__main__":
    solve()