中学生数学题[GDOI2016]

AK-dream

发布于：2020年3月2日

次浏览

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

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

商品的销量和商品的价格构成一个一次函数。假如商品的价格为$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;
}

更新于：2020年9月7日