XUJCOJ 1348 题解

题目简述:勇者的初始攻击力为 a,每次增长的攻击力为 b,恶龙的血量为 c,问勇者杀死恶龙至少需要多少个回合。

首先我们明确,勇者最优的打法一定是先增加攻击力(可能是零次),再打龙,也就是说,勇者的操作序列一定是若干次加攻 + 若干次攻击。

暴力思路:从零开始枚举加攻次数,直到攻击力大于等于恶龙血量时退出,期间维护最小值 ans,伪代码如下。

如果这样做的话只可以通过33%的样例,但是只要稍作修改,就可以通过66%。

如何修改呢?很简单,我们在暴力思路的基础上,维护 ans 的同时判断当前答案是否大于 ans,如果大于,则跳出循环。

到这里可能有同学会问了,为什么加一个 break 就能把 1e9 的那组数据也过了呢?接下来,为大家带来这道题的正确解法。

假设勇者增加攻击力的次数为 x,总共需要的回合数为 y,那么我们可以得到一个关于 x 和 y 的函数。

现在的问题就转化成,当 x ∈ Z 时,y 的最小值是多少。

我们在小学二年级的时候就知道,对勾函数的一般式如下:

很明显,我们要计算的函数就是由对勾函数进行伸缩平移后得到的。

对勾函数图像

看到这里,关于 <为什么加一个 break 就能通过66%的数据> 这个问题是不是已经得到了解决呢?

图像画出来以后,我们发现只需要求 y 的极小值点就可以了,自然想到了求导。

因为原函数中有一个向上取整符号,所以我们可以先求 y 的极小值点处 x 的值为多少,然后再通过 x 去计算 y,这样就可以避免向上取整在计算过程中带来的麻烦了。

复合函数求导
令导数等于零
移项
展开
整理

根据二次函数求根公式可以得到两个解,这里我们要更大的那个,因为对勾函数上半支的对称轴在下半支的对称轴右侧。

求根化简

得到 x 以后,我们只要比较 x 的左右五个整数点处 y 的值就可以了(这里其实只用考虑 x 和 x + 1 这两个点,但是保险起见多考虑几个)。注意,当 x 小于零时,即极小值点在 y 轴左侧,此时因为 x ∈ Z 所以 x 越大 y 越大,故在这种情况下只需要计算 x = 0 时的 y 就可以了。

评论已关闭

  • 写得很详细,感谢涂涂