【题目描述】
小明上初中了,他对数学有着很强烈的兴趣。
在小明学完一次函数之后,老师留了一道应用题:
商品的销量和商品的价格构成一个一次函数。假如商品的价格为$p$,愿意购买此商品的人数为$n$,他们之间满足$n=\lfloor n_0-kp\rfloor$,其中$p,k$为实数,$n,n_0$为整数,$\lfloor x\rfloor$表示不超过$x$的最大整数。
每个商品的成本为$p_0$,则销售利润为$n(p-p_0)$。请你选择一个合适的价格,使得销售利润最大。假设商品的数量无限制,未售出的商品对利润没有影响。
小明很快就做出来这道题,于是在哥哥大明面前表现的很得意。大明想了想,问小明:“如果你可以设置两个价格$p_1$和$p_2$$(p_1 > p_2)$,有$n_1 = \lfloor n_0-kp_1\rfloor$的人按价格$p_1$购买,$n_2 = \lfloor n_0-kp_2\rfloor - n_1$的人按价格$p_2$购买,此时如何设置这两个价格使得利润最大?”
小明想了想,很快又想出做法了,就跑去告诉哥哥大明。大明没时间检查小明的做法,于是找到了聪明的你。你能否帮大明写一个程序验证小明的答案?
【输入格式】
输入文件只有一行:一个整数$n_0$和两个实数$p_0$,$k$,具体含义见题目描述。
【输出格式】
输出文件一行:两个实数,分别表示设置一个价格的最大利润和设置两个价格的最大利润。
题解
一道友好的数学题
先看第一问 在$n$不变的条件下$p$显然是越大越好 所以$\lfloor n_0-kp\rfloor$会尽量小 那我们就可以把那个下取整丢掉了
奇妙变换一下 得到$p=\frac{n_0-n}{k}$
利润是$Y=n(p-p_0)$把$p=\frac{n_0-n}{k}$代入,得到$Y=-\frac{1}{k}n^2+(\frac{n0}{k}-p_0)n$这显然是一个关于$n$的二次函数 于是用三分法搞一下就可以了
第二问 假设$n_1$确定 那么第二件商品的利润也是个关于$n_2$的二次函数 然后总利润和$n_1$也会是个单峰函数的关系 具体就不证了 所以三分里再套个三分就行了
据说有$O(1)$解法 反正我太蒻了
代码
1 |
|