Codeforces1626C Monsters And Spells(双指针)
题目链接题意:N个怪物,出现时间是Ki 有着Hi的血量。 人蓄力释放魔法第k次时,伤害力为K,且魔法消耗值也为K,一个怪物只能打一次,问打败所有怪物所需的最少魔法值是多少。解析:考虑到是若干条直线一样的东西(抽象)我们定义一个直线的区间为【L,R】这个区间里面的怪物都能打败且从L时刻开始蓄力。那么如果我们倒着枚举,即Kn作为第一个区间的R,左端点很显然的算得出来,同理,计算Kn-1时,当且仅当 L<=Kn-1 必须合并这个区间,L取更小的端点值。struct pe{ ll