[BZOJ 1011] [HNOI2008] 遥远的行星 【近似解】

题目链接： BZOJ - 1011

题目分析

这道题的特别之处在于，答案可以有5%的误差。

嗯..So? 我还是不会，于是看题解。

神犇的题解就是利用这误差范围求一个近似解。

怎么求近似解呢？假如 g[i] 是第 i 个点受到的引力来源中最后的一个点。那么我们如果要直接求 f[i] （第i个点受到的引力）是要枚举 1 到 g[i] 。

然而如果我们直接从之前的一个 f[i - t] 为基础近似一下，再暴力计算 g[i - t] + 1 到 g[i] 的部分，就会大大节省时间了。

因为离得越远的行星带来的引力越小，所以 1 到 g[i - t] 的行星近似一下之后对 f[i] 答案的误差并不会很大。

怎么来近似呢？某位神犇推了如下公式：

其中 t 的取值越大，用时越长，但误差越小。我的代码中取了 t=100，但是经过试验，我这个代码改成 t=15 在BZOJ上依然可以 AC 。

代码

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

const int MaxN = 100000 + 5, t = 100;

typedef double DB;

int n;

int W[MaxN], g[MaxN];

DB A, Ans;

DB f[MaxN];

int main()

{

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

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

	{

		scanf("%d", &W[i]);

		g[i] = (int)(A * i + 1e-8);

	}

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

	{

		if (i <= t)

		{

			f[i] = 0.0;

			for (int j = 1; j <= g[i]; ++j)

				f[i] += (DB)W[j] / (DB)(i - j);

			f[i] *= (DB)W[i];

		}

		else

		{

			f[i] = f[i - t] / (DB)W[i - t] * ((DB)(i - t) - (DB)g[i - t] / 2.0) / ((DB)(i) - (DB)g[i - t] / 2.0);

			for (int j = g[i - t] + 1; j <= g[i]; ++j)

				f[i] += (DB)W[j] / (i - j);

			f[i] *= (DB)W[i];

		}

		printf("%.8lf\n", f[i]);

	}

	return 0;

}