P9181 题解
luyifan091120
·
·
题解
数学题+二分答案。
题目地址：P9181。
题目简述：
形式化的描述：给定 r_1,r_2,\dots,r_n，且 \sum\limits_{i=1}^n x_i=s，求 S=\dfrac{1}{2}\sum\limits_{i=1}^n x_i\sqrt{r_i^2-x_
i^2} 的最大值。
做法分析：
首先，我们先介绍一下拉格朗日乘数法。
设给定 n 元函数 z=f(x_1,x_2,\dots,x_n) 和附加条件 \varphi(x_1,x_2,\dots,x_n)=0，为寻找 z=f(x_1,x_2,\dots,x_n) 在附加条件下的极值点，先写出拉格朗日函数：F(x_1,x_2,\dots,x_n,\lambda)=f(x_1,x_2,\dots,x_n)+\lambda\varphi(x_1,x_2,\dots,x_n)，其中 \lambda 为参数。
接着对 x_1,x_2,\dots,x_n,\lambda 分别求偏导数：
\begin{cases}F'_{x_1}=f'_{x_1}(x_1,x_2,\dots,x_n)+\lambda\varphi'_{x_1}(x_1,x_2,\dots,x_n)\\F'_{x_2}=f'_{x_2}(x_1,x_2,\dots,x_n)+\lambda\varphi'_{x_2}(x_1,x_2,\dots,x_n)\\\dots\\F'_{x_n}=f'_{x_n}(x_1,x_2,\dots,x_n)+\lambda\varphi'_{x_n}(x_1,x_2,\dots,x_n)\\F'_{\lambda}=\varphi_(x_1,x_2,\dots,x_n)\end{cases}
则满足：\begin{cases}F'_{x_1}=0\\F'_{x_2}=0\\\dots\\F'_{x_n}=0\\F'_{\lambda}=0\end{cases} 的 \{x_1,x_2,\dots,x_n\} 即为可能的取等条件。
回到本题，即在约束条件 \varphi(x_1,x_2,\dots,x_n)=\sum\limits_{i=1}^n x_i-s=0 的约束条件下，求 z=f(x_1,x_2,\dots,x_n)=\sum\limits_{i=1}^n x_i\sqrt{r_i^2-x_
i^2} 的最大值，答案即为 \dfrac{1}{2}z_{max}。
构造拉格朗日函数：
&=\sum\limits_{i=1}^n x_i\sqrt{r_i^2-x_
i^2}+\lambda(\sum\limits_{i=1}^n x_i-s)
\end{aligned}$。
则应该有：$\begin{cases}F'_{x_1}=\dfrac{r_1^2-2x_1^2}{\sqrt{r_1^2-x_1^2}}+\lambda=0\\F'_{x_2}=\dfrac{r_2^2-2x_2^2}{\sqrt{r_2^2-x_2^2}}+\lambda=0\\\dots\\F'_{x_n}=\dfrac{r_n^2-2x_n^2}{\sqrt{r_n^2-x_n^2}}+\lambda=0\\F'_{\lambda}=\sum\limits_{i=1}^n x_i-s=0\end{cases}$。
我们记 $k=-\lambda$，则有：
$\dfrac{r_1^2-2x_1^2}{\sqrt{r_1^2-x_1^2}}=\dfrac{r_2^2-2x_2^2}{\sqrt{r_2^2-x_2^2}}=\dots=\dfrac{r_n^2-2x_n^2}{\sqrt{r_n^2-x_n^2}}=k$。
解得：
$x_i^2=
\dfrac{4r_i^2-k^2-k\sqrt{8r_i^2+k^2}}{8}$。
又 $\dfrac{4r_i^2-k^2-k\sqrt{8r_i^2+k^2}}{8}$ 有可能小于 $0$，此时对应的 $x_i$ 不是实数，此时可设 $x_i=0$，即对 $S$ 的贡献为 $0$（因为不存在满足条件的 $x_i$）。
故：
$x_i=\begin{cases}0,\dfrac{4r_i^2-k^2-k\sqrt{8r_i^2+k^2}}{8}<0\\\sqrt{\dfrac{4r_i^2-k^2-k\sqrt{8r_i^2+k^2}}{8}},otherwise\end{cases}$。
最后，对 $k$ 进行二分，找出最小的 $k$，使得 $\sum\limits_{i=1}^n x_i<s$。
最后贴上 AC 代码：
```cpp
#include<bits/stdc++.h>
#define aa (4*r[i]*r[i]-k*k-k*sqrt(8*r[i]*r[i]+k*k))/8
#define eps 1e-9
long long n;
double s;
double r[100005];
double calc(double k){//计算面积的两倍
double sum=0;
for(int i=1;i<=n;++i){
if(aa<0) continue;
sum+=sqrt(aa)*sqrt(r[i]*r[i]-aa);
}
return sum;
}
double check(double k){//判断是否满足条件
double len=0;
for(int i=1;i<=n;++i){
if(aa<0) continue;
len+=sqrt(aa);
}
if(len>s) return 0;
else return 1;
}
using namespace std;
int main(){
scanf("%lld%lf",&n,&s);
for(int i=1;i<=n;++i) scanf("%lf",&r[i]);
double l,rr,mid;
l=0,rr=100000;
while(rr-l>eps){//二分
mid=(l+rr)/2;
if(check(mid)) rr=mid;
else l=mid;
}
printf("%.10lf",calc(l)/2);
return 0;
}
```