P2729题解

· · 题解

其实，谁说本题爆搜就一定要特别处理有0的情况了？
作为一名数竞生，我们自有方法。

【数竞党必备知识】
柯西不等式：
对于实数a_1,a_2,...,a_n和b_1,b_2,...,b_n，有：

\left( \sum_{k=1}^n a_k b_k \right)^2 \leq \left( \sum_{k=1}^n a_k^2 \right) \left( \sum_{k=1}^n b_k^2 \right).

特别地，令n=3，得到柯西不等式的一个特例：

(ax+by+cz)^2\leq (a^2+b^2+c^2)(x^2+y^2+z^2).

等号成立当且仅当a,b,c与x,y,z两组数成比例。（0:0也算成比例，但是0:1不算）

这样，我们妙用等号成立条件：
“若(ax+by+cz)^2=(a^2+b^2+c^2)(x^2+y^2+z^2)，则a,b,c与x,y,z两组数成比例。”并且其逆命题也成立。

回到本题，令a,b,c分别为三种饲料的混合后的比例（样例里的21:28:35），x,y,z分别为欲求饲料的比例（样例里的3:4:5），对其用柯西不等式即可。

代码示意如下：

#define squ(x) ((x)*(x))
if ((squ(a)+squ(b)+squ(c))*(squ(x)+squ(y)+squ(z))==squ(a*x+b*y+c*z)){
    //do something...
}

这样就避免了对0的判断。