Average Superhero Gang Power

http://codeforces.com/contest/1111/problem/B

Every superhero has been given a power value by the Felicity Committee. The avengers crew wants to maximize the average power of the superheroes in their team by performing certain operations.

Initially, there are nn superheroes in avengers team having powers a1,a2,…,ana1,a2,…,an , respectively. In one operation, they can remove one superhero from their team (if there are at least two) or they can increase the power of a superhero by 11 . They can do at most mm operations. Also, on a particular superhero at most kk operations can be done.

Can you help the avengers team to maximize the average power of their crew?

Input

The first line contains three integers nn , kk and mm (1≤n≤1051≤n≤105 , 1≤k≤1051≤k≤105 , 1≤m≤1071≤m≤107 ) — the number of superheroes, the maximum number of times you can increase power of a particular superhero, and the total maximum number of operations.

The second line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1061≤ai≤106 ) — the initial powers of the superheroes in the cast of avengers.

Output

Output a single number — the maximum final average power.

Your answer is considered correct if its absolute or relative error does not exceed 10−610−6 .

Formally, let your answer be aa , and the jury's answer be bb . Your answer is accepted if and only if |a−b|max(1,|b|)≤10−6|a−b|max(1,|b|)≤10−6 .

Examples

Input

Copy

2 4 6
4 7

Output

Copy

11.00000000000000000000

Input

Copy

4 2 6
1 3 2 3

Output

Copy

5.00000000000000000000

Note

In the first example, the maximum average is obtained by deleting the first element and increasing the second element four times.

In the second sample, one of the ways to achieve maximum average is to delete the first and the third element and increase the second and the fourth elements by 22 each.

 

并不是删得只留下最大的就好了,比如3 2 10     1 1 1最好是删一个留两个。

枚举删的个数,对于确定删的个数,留下最大的那些,删去小的。

对于确定要留下几个,加到哪个上都是一样的,因为平均=总和/个数 

可以o(n)枚举,也可以三分,因为平均值关于删的个数是单峰函数。

暴力:

#include<bits/stdc++.h>
using namespace std;
#define ll long long

int n,k,m;
int a[100000+1000]; 
ll sum[100000+1000];
double ans;

bool cmp(int a,int b){return a>b;}

double check(int cnt)
{
	int deleted=n-cnt;
	double maxn=min((ll)m-deleted,(ll)cnt*k);
	return (maxn+sum[cnt])/cnt;
}

int main()
{
//	freopen("input.in","r",stdin);
	cin>>n>>k>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i];
	for(int i=max(1,n-m);i<=n;i++)
	{
		ans=max(ans,check(i));
	}
	printf("%.10f\n",ans);
	return 0;	
}

三分:

#include<bits/stdc++.h>
using namespace std;
#define ll long long

int n,k,m;
int a[100000+1000]; 
ll sum[100000+1000];
double ans;

bool cmp(int a,int b){return a>b;}

double check(int cnt)
{
	int deleted=n-cnt;
	double maxn=min((ll)m-deleted,(ll)cnt*k);
	return (maxn+sum[cnt])/cnt;
}

int main()
{
//	freopen("input.in","r",stdin);
	cin>>n>>k>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i];
	
	int l=max(1,n-m),r=n,m1,m2;
	while(l<=r)
	{
		m1=l+(r-l)/3,m2=r-(r-l)/3;
		if(check(m2)>check(m1)){ans=check(m2);l=m1+1;}
		else {ans=check(m1);r=m2-1;}
	}
	printf("%.10f\n",ans);
	return 0;	
}

 

全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 14:08
点赞 评论 收藏
分享
程序员牛肉:主要是因为小厂的资金本来就很吃紧,所以更喜欢有实习经历的同学。来了就能上手。 而大厂因为钱多,实习生一天三四百的就不算事。所以愿意培养你,在面试的时候也就不在乎你有没有实习(除非是同级别大厂的实习。) 按照你的简历来看,同质化太严重了。项目也很烂大街。 要么换项目,要么考研。 你现在选择工作的话,前景不是很好了。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务