[cf] Educational Codeforces Round 125 D. For Gamers. By Gamers.

前言

传送门 :

思路

每个雇佣兵 : c i , d i , h i c_i,d_i,h_i ci​,di​,hi​ 每次战斗你都可以招 单种多个雇佣兵

每个小怪 : D i , H i D_i,H_i Di​,Hi​

考虑我们枚举每一个 i i i

那么被杀死的时间就是 h i / D h_i/D hi​/D

我们需要在这个时间之前杀死这个怪 则 H d i ∗ x < h i D \frac{H}{d_i*x} \lfloor \frac{H*D}{h_i*d_i} \rfloor+1 x>⌊hi​∗di​H∗D​⌋+1

如果直接枚举显然失智

假设我们现在 招了 t t t 个

那么 ⌊ H ∗ D h i ∗ d i ⌋ + 1 < = t \lfloor \frac{H*D}{h_i*d_i} \rfloor+1 C; for(int i = 0 ;i>c[i]>>d[i]>>h[i]; pv[c[i]] = max(pv[c[i]],d[i]*h[i]); //求每个C[I] 最大的d[i]*h[i] } for(int i=1;iD>>H; ll v = D*H; int ans = lower_bound(md,md+C+1,v) -md; //二分查找答案 if(ans >C){ cout