给定一个序列，要求相邻两个数至少选一个，求选出数的最大平均数和最大中位数
\(\text{sol}\)：二分答案。
二分平均数\(\text{mid}\)，将每个元素减去\(\text{mid}\)，\(\text{DP}\)一遍求能选的最大总和，大于等于\(\text{0}\)即\(true\)
二分中位数\(\text{mid}\)，小于\(\text{mid}\)的值记为\(-1\)，大于等于\(\text{mid}\)的值记为\(1\)，求选出最大总和，大于\(0\)即\(true\)（由于这里中位数取\(\lceil \frac{n}{2} \rceil\)）
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
#define MAXN (int)(1e5+233)
#define MAXA (long long)(1e9+233)
int a[MAXN];
long long c[MAXN],b[MAXN];
int n;
long long maxn=0;
inline long long maxw(long long A,long long B) { return A>B?A:B; }
long long f[MAXN];
inline bool check_average(long long x)
{
for (int i=1;i<=n;i++) b[i]=c[i]-x;
// if (x==43333) for (int i=1;i<=n;i++) printf("%lld ",b[i]); puts("");
f[1]=b[1]; f[2]=maxw(b[2],b[1]+b[2]);
for (int i=3;i<=n;i++) f[i]=maxw(f[i-2],f[i-1])+b[i];
// if (x==43333) for (int i=1;i<=n;i++) printf("%lld ",f[i]); puts("");
return f[n-1]>=0||f[n]>=0;
}
inline double bina_average()
{
long long l=1,r=maxn*100000,mid;
while (l<r)
{
mid=((l+r+1)>>1);
if (check_average(mid)) l=mid;
else r=mid-1;
}
return ((double)(l))/100000.0000;
}
inline bool check_median(int x)
{
f[1]=(int)(a[1]>=x?1:-1); f[2]=(int)(a[2]>=x?1:-1); if (f[1]==1) f[2]++;
for (int i=3;i<=n;i++)
f[i]=maxw(f[i-1],f[i-2])+(a[i]>=x?1:-1);
return f[n-1]>0||f[n]>0;
}
inline int bina_median()
{
int l=1,r=maxn,mid;
while (l<r)
{
mid=((l+r+1)>>1);
if (check_median(mid)) l=mid;
else r=mid-1;
}
return l;
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
maxn=maxw(maxn,a[i]);
c[i]=a[i]*1ll*100000;
}
printf("%.5lf\n%d\n",bina_average(),bina_median());
return 0;
}
