当前位置: 代码迷 >> 综合 >> Codeforces Round #537 (Div. 2)B. Average Superhero Gang Power (贪心+暴力)
  详细解决方案

Codeforces Round #537 (Div. 2)B. Average Superhero Gang Power (贪心+暴力)

热度:37   发布时间:2023-11-15 13:02:45.0

题目链接:http://codeforces.com/contest/1111/problem/B

#include<bits/stdc++.h>
using namespace std;#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define ll long long#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define root l,r,rt
#define mst(a,b) memset((a),(b),sizeof(a))
#define pii pair<ll,ll>
#define mk(x,y) make_pair(x,y)
const int maxn=1e5+9;
const int mod=998244353;
const int ub=1e6;
ll powmod(ll x,ll y){ll t; for(t=1;y;y>>=1,x=x*x%mod) if(y&1) t=t*x%mod; return t;}
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
/*
题目大意:给定一个长度为n的序列,要求可以执行m次操作,
每次操作可以把一个人的权值加一,可以删除一个人(如果删除后人数不为空),
但每个人增长的权值最大值为k,问执行操作后其序列平均值是多少。题目分析:贪心,假设删除了x次,增长了y次,
其删除的肯定是数值最小的,所以把原数组排个序,然后枚举删除的次数即可。
时间复杂度:O(n).
*/ll a[maxn];
ll sum[maxn];
ll n,k,m;int main()
{cin>>n>>k>>m;sum[0]=0LL;for(int i=1;i<=n;i++) cin>>a[i];sort(a+1,a+n+1);rep(i,1,n+1) sum[i]=sum[i-1]+a[i];double ans=1.0*sum[n]/n;rep(i,0,n) if(i<=m){int tm=m-i;ans=max(ans,1.0*(sum[n]-sum[i]+1.0*min(1LL*tm,(n-i)*k))/(n-i));}else break;printf("%.7f\n",ans);return 0;
}

 

  相关解决方案