ABC 263 E
题意
从一个大小为n的数组选一些数,选的限制是:
对于\(1 \leq i \leq n-1\),\(a_i\)或者\(a_{i+1}\)被选。
问题1:求符合题意要求的选法中最大平均数
问题2:求符合题意要求的选法中最大的中位数
思路
第一问很好解决,二分平均数,然后check函数写下dp就好了
第二问真的没想明白,看看大神的代码后,居然还是二分
二分中位数,然后check函数遍历数组,返回值res,当遇到大于中位数x的数,res+1,当遇到小于中位数x的数,判断是否能不选它,这里要用pre记录上一个小于中位数x且不选的位置,如果pre等于前一位,那么当前位只能选,res--,否则pre更新为当前位。
代码
bool check1(double x)
{
f[0][0]=f[0][1]=0;
for(int i=1;i<=n;i++)
{
f[i][0]=max(f[i-1][0],f[i-1][1])+a[i]-x;
f[i][1]=f[i-1][0];
}
if(f[n][0]>0||f[n][1]>0) return true;
return false;
}
bool check2(int x)
{
int pre=-1;
int res=0;
for(int i=1;i<=n;i++)
{
if(a[i]>=x) res++;
else
{
if(pre==i-1) res--;
else pre=i;
}
}
return res>0;
}
void solve()
{
cin>>n;
double sum=0;
for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i];
//max average
double l=0,r=sum;
while(r-l>eps)
{
double mid=(l+r)/2;
if(check1(mid)) l=mid;
else r=mid;
}
printf("%.6lf\n",l);
//max mediam
int L=0,R=1e9;
while(L<R)
{
int mid=(L+R+1)>>1;
if(check2(mid)) L=mid;
else R=mid-1;
}
printf("%lld\n",L);
}
标签:pre,int,res,中位数,mid,else,ABC236
From: https://www.cnblogs.com/LIang2003/p/17145537.html