AcWing 3578. 最大中位数
原题链接
中等
作者:
Moccept
,
2024-04-13 00:06:42
,
所有人可见
,
阅读 1
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N=200010;
int n,m;
int w[N];
bool check(int mid)
{
LL res=0;
for(int i=n/2;i<n;i++)
if(w[i]<mid)
res+=mid-w[i];
return res<=m;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++) scanf("%d",&w[i]);
sort(w,w+n);
int l=0,r=2e9;
while(l<r)
{
int mid=(LL) l+r+1>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
printf("%d\n",r);
return 0;
}
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const double eps=1e-5;
double cube_root(double x)
{
double l=0,r=x;
while(r-l>eps)
{
double mid=(l+r)/2;
if(mid*mid*mid<x)
{
l=mid;
}
else
{
r=mid;
}
}
return l;
}
int main()
{
int T;
cin>>T;
while(T--)
{
int x;
cin>>x;
double ans = cube_root(x);
printf("%.3f\n",ans);
}
return 0;
}