CF68B Energy exchange

题面

有 \(n\) 个电池，每个初始电量为 \(a_{i}\)，现在需要通过能量传递让所有电池电量相等。能量传递的方法是：选择两个电池，一个失去 \(x\) 电量（\(x\) 可以不是整数），另一个得到 $ x-\dfrac{xk}{100}$ 点电量。也就是说，传递过程中会损失 \(k\%\) 的电量。

现给出 \(a_{i}\)，求通过能量传递能获得的最大单个电量（所有电池电量要求相等）。

思路

很明显的二分，每次二分最终能获得的最大单个电量即可

注意到，例如最后要让每一个电池的电量都变味\(x\)，那么对于每一个\(a_i\)，就会有两种情况，一种是需要补充，一种是可以给别的补充

现在假设所有电量大于\(x\)电池可以给别的电池输送\(t\)的电量（不计损耗），那么最终算上损耗就是\(t\times \dfrac{100-k}{100}\)

最后看看能够补充的是否大于等于需要补充的

还有一点，为什么是大于等于而不是严格等于呢？即使我需要补充比需要补充的还要多，但是多出来的也可以通过不断地转移，最终变为一个极小值直到忽略不计，所以是大于等于，而不是严格等于

代码

#include<bits/stdc++.h>
using namespace std;
const int Maxn=1e5+10;
long long a[Maxn];
long long n,k,maxn;
bool check(long long x)
{
	long long cnt=0,sum=0;
	for(int i=1;i<=n;i++)
	{
		if(a[i]>x) cnt+=a[i]-x;
		else sum+=x-a[i];
	}
	return (cnt*k/100)>=sum;
}
int main()
{
	cin>>n>>k;
	k=100-k;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		a[i]*=1e7;
		maxn=max(maxn,a[i]);
	}
	long long l,r,mid,ans;
	l=0,r=maxn;
	while(l<=r)
	{
		mid=(l+r)>>1;
//		cout<<l<<" "<<r<<" "<<mid<<endl;
		if(check(mid)) l=mid+1,ans=mid;
		else r=mid-1;
	}
	printf("%.8f",(double)ans/1e7);
 }