11111111
zhangslover
·
·
题解
CF1805C
本题解用的是初高中知识，以初二牲的方式思考编写
题目描述
给定 n 个正比例函数 y=kx，再给出 m 个下凸二次函数 y=ax^2+bx+c(a>0)，对于每个二次函数，从给定中找出一个一次函数，使得两函数图像没有交点。
**核心知识：一元二次方程无解的条件，一次函数，二次函数，二分。**
-----------
## 思路
首先，二次函数 $y=ax^2+bx+c$ 与一次函数 $y=kx$ 的交点的横坐标就是方程 $ax^2+bx+c=kx$ 的解。
我们将原方程移项，提公因式，可以变为 $ax^2+(b-k)x+c=0$ 的一元二次方程。
（其中 $a=a,b=b-k,c=c$ )
而题目要求两函数图像无交点，即这个方程无实数解。
为什么呢？我们来回想一下数轴能表示的数的范围：实数。
也就是说，数轴不能表示虚数。而平面直角坐标系是由两条数轴组成的，两条函数又交在这个坐标系里。
**言外之意，两函数交点的横坐标不可能为复数**
现在来让我们回想一下一元二次方程解的三种情况：
1. 当 $\Delta>0$，方程有两个不相等的实数根。
2. 当 $\Delta=0$，方程有两个相等的实数根。
3. 当 $\Delta<0$，方程在虚数范围内有两个共轭复根。（如果没学过，可以视为无解）
其中 $\Delta=b^2-4ac$.
回到题目的条件，要是使方程 $ax^2+(b-k)x+c=0$ 无解，只需要使 $\Delta<0$ 就可以了。
而这个式子的 $\Delta$ 化简即为
$$ (b^2-4ac)-(2bk-k^2)$$
而由于 $(b^2-4ac)$ 是定值，要想使这一串式子最小，那么就让 $(2bk-k^2)$ 最大就可以了。
我们设一个以 $k$ 为自变量的函数 $y=-k^2+2bk$, 因为二次项系数 $-1<0$,所以抛物线开口向下。
且通过配方我们可以把这个式子化成形如 $y=a(x-h)^2+k$ 的式子（由二次函数图像性质我们知道 $h$ 为对称轴，顶点坐标为 $(h,k)$）:
$$ y=a(x+\frac{b}{2a})^2+\frac{4ac-b^2}{4a}$$
$$ =a(x-\frac{2b}{2})^2+\frac{4b^2}{4}$$
$$ =a(x-b)^2+b^2 $$
其中 $h=b,k=b^2
所以：
- 当 k<h 时，y 随 k 的增大而增大。
- 当 k>h 时，y 随 k 的增大而减小。
得到了这样的一个关系之后，我们就可以二分找出使函数最大的 k 的值，带入 \Delta 验证是否小于 0 即可