abc236_e

abc236_e

二分+判断
如果是平均数，我们只需将每个数-mid，然后dp判断是和是否大于等于0即可
如果是中位数，那么我们将a[i]<mid看作-1，a[i]>=mid看作1，然后dp判断是否大于0即可

#include<algorithm>
#include<cstdio>
#include<cstring>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
using namespace std;
typedef long long ll;
typedef double db;

const db eps=1e-10;
const int N=1e5+5;
const ll mo=998244353;
const db inf=1ll<<60;
const db INF=1ll<<60;
ll a[N],d[N],e[N];
ll n,x,mx,tot;
db l,r,mid,b[N],f[N][2],c[N];
ll g[N][2];

bool bz[N];


bool check(db x){
    fo(i,0,n) fo(j,0,1) f[i][j]=-inf;
    fo(i,1,n) b[i]=c[i]-x;

    f[1][0]=0;
    f[1][1]=b[1];
    fo(i,2,n) {
        f[i][0]=f[i-1][1];
        f[i][1]=max(f[i-1][0], f[i-1][1])+b[i];
    }

    return (max(f[n][0], f[n][1]) >eps);
    
}
bool pd(ll x){
	fo(i,1,n) {
		if (e[i]<x) d[i]=-1;
		else d[i]=1;
	}
	fo(i,1,n) fo(j,0,1) g[i][j]=-INF;
	
	g[1][0]=0;
	g[1][1]=d[1];
	
	fo(i,2,n) {
		g[i][0]=g[i-1][1];
		g[i][1]=max(g[i-1][0], g[i-1][1])+d[i];
		
//		printf("%d %lld %lld\n",i,g[i][0], g[i][1]);
	}
	return (max(g[n][0],g[n][1])>0);
	
}
void solve(){
	int l=1,r=n,mid;
	
	while (l<r) {
		mid=(l+r+1)>>1;
		if (pd(a[mid])) l=mid;
		else r=mid-1;
	}
	
	printf("%lld",a[l]);
}
int main() {
   
//	freopen("data.in","r",stdin);

    scanf("%lld",&n);
    fo(i,1,n) {
        scanf("%lld",&a[i]);
        mx=max(mx,a[i]);

        c[i]=a[i];
        e[i]=a[i];
    }
    sort(a+1,a+n+1);
    
    l=0; r=mx;
    fo(i,1,200){
        mid=(l+r)/2.0;
        if (check(mid)) l=mid;
        else r=mid;
    }

    printf("%.9f\n",l);
    
    
	solve();

    return 0;
}