【BZOJ1011】【HNOI2008】遥远的行星 误差分析

题目大意

　　给你\(n,b\)，还有一个数列\(a\)。

　　对于每个\(i\)求\(f_i=\sum_{j=1}^{bi}\frac{a_ja_i}{i-j}\)。

　　绝对误差不超过\(5\%\)就算对。

　　\(0.01\leq b\leq 0.05,n\leq {10}^5\)　　

题解

　　我好像在以前的UR做过一道用误差来搞事情的题：【UER#7】天路

　　这题网上很多代码算出来的答案误差太大了。比如说\(n={10}^5,b=0.35,a_1=a_n={10}^7,\)其他的是\(0\)。这些代码会给出\(f_n=1212121212.121212\)，但实际上\(f_n=1000010000.1\)。

　　这道题的正确做法也是对于每一个\(i\)把\(j\)分段，只不过不是分成\(1\)段，而是分成好几段。对于同一段内的\(j\)满足\(\frac{1}{i-j_1}<1.05\times\frac{1}{1-j_2}\)，这样取\(j_1\)代替组内的\(j\)来计算误差就不会超过\(5\%\)了。（其实也可以让组内误差\(<\frac{1.05}{0.95}\)）。

　　时间复杂度：\(O(n)\)。

代码

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cstdlib>

#include<ctime>

#include<utility>

#include<cmath>

#include<functional>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int,int> pii;

typedef pair<ll,ll> pll;

void sort(int &a,int &b)

{

	if(a>b)

		swap(a,b);

}

void open(const char *s)

{

#ifndef ONLINE_JUDGE

	char str[100];

	sprintf(str,"%s.in",s);

	freopen(str,"r",stdin);

	sprintf(str,"%s.out",s);

	freopen(str,"w",stdout);

#endif

}

int rd()

{

	int s=0,c;

	while((c=getchar())<'0'||c>'9');

	do

	{

		s=s*10+c-'0';

	}

	while((c=getchar())>='0'&&c<='9');

	return s;

}

int upmin(int &a,int b)

{

	if(b<a)

	{

		a=b;

		return 1;

	}

	return 0;

}

int upmax(int &a,int b)

{

	if(b>a)

	{

		a=b;

		return 1;

	}

	return 0;

}

int b[100010];

double c[100010];

double a[100010];

double s[100010];

int main()

{

	open("bzoj1011");

	int n;

	double x;

	scanf("%d%lf",&n,&x);

	int i,j;

	int m=floor(x*n);

	int t=0;

	for(i=0;i<=m;i++)

		c[i]=double(n)/(n-i);

	for(i=1;i<=m;i++)

		if(i==m||c[i]>c[b[t]]*1.04)

			b[++t]=i;

	for(i=1;i<=n;i++)

	{

		scanf("%lf",&a[i]);

		s[i]=s[i-1]+a[i];

		int last=0;

		double ans=0;

		for(j=1;j<=t;j++)

		{

			int now=floor(double(b[j])/n*i);

			now=min(now,i-1);

			ans+=a[i]*(s[now]-s[last])/(i-last-1);

			last=now;

		}

		printf("%.10lf\n",ans);

	}

	return 0;

}