2 seconds
256 megabytes
standard input
standard output
It is well known that the planet suffers from the energy crisis. Little Petya doesn't like that and wants to save the world. For this purpose he needs every accumulator to contain the same amount of energy. Initially every accumulator has some amount of
energy: the i-th accumulator has
ai units of energy. Energy can be transferred from one accumulator to the other. Every timex units of energy are transferred (x
is not necessarily an integer)k percent of it is lost. That is, if
x units were transferred from one accumulator to the other, amount of energy in the first one decreased byx units and in other increased by
units.
Your task is to help Petya find what maximum equal amount of energy can be stored in each accumulator after the transfers.
First line of the input contains two integers n andk (1 ≤ n ≤ 10000, 0 ≤ k ≤ 99) — number of accumulators and the percent of energy
that is lost during transfers.
Next line contains n integers
a1, a2, ... , an — amounts of energy in the first, second, ..,n-th accumulator respectively
(0 ≤ ai ≤ 1000, 1 ≤ i ≤ n).
Output maximum possible amount of energy that can remain in each of accumulators after the transfers of energy.
The absolute or relative error in the answer should not exceed
10 - 6.
3 50 4 2 1
2.000000000
2 90 1 11
1.909090909
二分求最大，我的做法是先把数组从大到小排列，在二分的时候判断，如果 当前的能量已经大于最大值，那我们可以从中拿出多余的那部分，积累起来；否则，分配积累的能量给它，我们假设它需要t能量，那么真正需要的能量就是t*100/(100-k)；，假如处理到某个i时，积累的能量不够使它达到我们要的最大值，那么就说明这么最大值太大了，要小一点，如果处理完所有的，说明最大值还可以再大，如此下去就能找到答案了，但是对于所有数都相同的情况，一开始我没注意,WA了， 之后加了个判断就过了
#include<map>
#include<set>
#include<list>
#include<stack>
#include<queue>
#include<vector>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
double ener[10010];
int cmp(double a, double b)
{
return a > b;
}
int main()
{
int n, k;
while(~scanf("%d%d", &n ,&k))
{
bool flag = false;
for(int i = 0; i < n; i++)
{
scanf("%lf", &ener[i]);
if(i >= 1)
{
if(ener[i] != ener[i - 1])
{
flag = true;
}
}
}
if(n == 1 || !flag )
{
printf("%.9f\n", ener[0]);
continue;
}
sort(ener, ener + n,cmp);
double l = ener[n - 1];
double r = ener[0];
double mid;
double ans;
while( r - l > 1e-9 )
{
bool flag = true;
double cur_ener = 0;
mid = (l + r) / 2;
for(int i = 0; i < n; i++)
{
if(ener[i] - mid >= 1e-9)
cur_ener += (ener[i] - mid);
else
{
double dis = 1.0 * (mid - ener[i]) * 100 / (100 - k);
if(dis - cur_ener > 1e-9)
{
flag = false;
break;
}
else
cur_ener -= dis;
}
}
if(flag)
{
ans = mid;
l = mid;
}
else
r = mid;
}
printf("%.9f\n", ans);
}
return 0;
}