AK-dream

【题目描述】
小明上初中了,他对数学有着很强烈的兴趣。

在小明学完一次函数之后,老师留了一道应用题:

商品的销量和商品的价格构成一个一次函数。假如商品的价格为$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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;

int n0;
double k, p0;

inline double calc(int n2, int n1) {
double p = (n1 - n2) * 1.0 / k;
return n2 * (p - p0);
}

inline double solve(int n1) {
double p = (n0 - n1) * 1.0 / k;
int l = 1, r = n0 - n1;
while (l < r) {
int m1 = l + (r - l) / 3, m2 = m1 + (r - l) / 3 + 1;
if (calc(m1, n0 - n1) < calc(m2, n0 - n1)) l = m1 + 1;
else r = m2 - 1;
}
return n1 * (p - p0) + calc(l, n0 - n1);
}

int main() {
scanf("%d %lf %lf", &n0, &p0, &k);
printf("%.3lf ", solve(0));
int l = 1, r = n0;
while (l < r) {
int m1 = l + (r - l) / 3, m2 = m1 + (r - l) / 3 + 1;
if (solve(m1) < solve(m2)) l = m1 + 1;
else r = m2 - 1;
}
printf("%.3lf", solve(l));
return 0;
}


 评论