3050379_wa.c

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <math.h>
#define max 100001

double w[max], d[max], sum[max], a[max];;
int p[max], n, l;

void drs_point()
{
	int i;

	for(i = n; i > 0; i--)
	{
		p[i] = i;
		w[i] = a[i];
		d[i] = 1;
		while(p[i]<n&&w[i]/d[i]<=w[p[i]+1]/d[p[i]+1])
		{
			w[i] = w[i]+w[p[i]+1];
			d[i] = d[i]+d[p[i]+1];
			p[i] = p[p[i]+1];
		}
	}
}

double ave(int i,int j)
{
	return (sum[j]-sum[i]+a[i])/(j-i+1);
}

int min(int a,int b)
{
	return a < b ? a : b;
}

int pk(int k,int j)
{
	if(k==0)
		return p[j];
	return min(n,pk(k-1,pk(k-1,j)+1));
}

int locate(int i,int j)
{
	int k, t;

	for(k = (int)ceil((log10(l)/log10(2))); k >= 0; k--)
	{
		if(j >= n || ave(i,j) >= ave(j+1,p[j+1]))
		{
			return j;
		}
		t = pk(k,j+1);
		if(t < n&&ave(i,t)<ave(t+1,p[t+1]))
			j = t;
	}
	if(j < n && ave(i,j)<ave(j+1,p[j+1]))
		j = p[j+1];
	return j;
}

int main()
{
	int i, j, m;
	double ans, tmp;

	scanf("%d%d",&n,&l);
	sum[0] = 0;
	for(i = 1; i <= n; i++)
	{
		scanf("%lf",&a[i]);
		sum[i] = sum[i-1]+a[i];
	}
	drs_point();
	m = n-l+1;
	ans = -1;
	for(i = 1; i <= m; i++)
	{
		j = i+l-1;
		if(ave(i,j)<ave(j+1,p[j+1]))
		{
			j = locate(i,j);
		}
		tmp = ave(i,j);
		if(tmp - ans > 0)
		{
			ans = tmp;
		}
	}
	printf("%d\n",(int)floor((ans*1000)));
	return 0;
}