自动搬运

查看原文

来自洛谷，原作者为

	luyifan091120 **

搬运于2025-08-24 22:46:06，当前版本为作者最后更新于2023-11-14 16:09:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

数学题+二分答案。

题目地址：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}$。

构造拉格朗日函数：

$\begin{aligned}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)\\ &=\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 代码：

#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;
}