题解：AT_abc303_f [ABC303F] Damage over Time

Laisira · 2025-01-16 11:13:57 · 题解

这道题感觉是贪心加二分，二分答案 ans，先肯定是用 t_{i}\times d_{i} 最高的打他。

设当前时间为 x，有的 t_i 贡献不完，要与 ans-x+1 取最小值。

否则考虑枚举时间，枚举时间肯定不能挨着枚举，由于最大值的可能更新只有 O(n) 个,于是离散了枚举。

每次的最大值表示为：

• t_i \leq ans-x+1$，$\max(t_i\times d_i)
• t_i > ans-x+1$，$\max((ans-x+1)\times d_i)

分别维护一下 t_i 大于和小于 ans-x+1 的最大值就行了，平衡树、线段树或者单纯的排个序都可以做。

然后把最大的总贡献算出来，最后判断与 H 的大小就行了。