[bzoj 1011] [HNOI2008]遥远的行星：近似算法（一种正确性显然的非乱搞的科学做法）

本文主要是介绍[bzoj 1011] [HNOI2008]遥远的行星：近似算法（一种正确性显然的非乱搞的科学做法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：给N个数Mi（1≤N≤10^5, 0≤Mi≤10^7）和实数a（0.01<a≤0.35），对每个1≤i≤N求 $\sum_{j=1}^{ai}\frac {M_iM_j} {i-j}$ ，相对误差不超过5%即可。

这种形式的和式不太好处理，也许用到某种奇妙的求和顺序、递推关系、或者数据结构？扫了一眼题解，黄学长的代码很短同时表示“这种题到底是什么鬼”，有题解标题为“根据所允许的误差进行模糊DP”。看来“误差不超过5%”的条件并不像我所以为的那样只是由于浮点误差……对于浮点误差而言，允许5%的相对误差似乎有点大？Too young, too simple, sometimes native……

于是又想了想。初中初识放缩法，对1/100+1/101+…+1/120这样的和式进行分组，组中的数用组内最大或最小的数替代，得出范围。组分多了难算，分少了范围太松，常常需要进一步调整。本题能不能运用这种思想呢？1/99999和1/100000相差并不大。

既然允许5%的误差是关键，那就来算一算。可以把答案调小，也可以调大，这里就调大好了。

设 $y > x$ ，则 $\frac 1 y < \frac 1 x$ ，为了用 $\frac 1 x$ 代替 $\frac 1 y$ ，须满足 $\frac 1 x \le (1+5\%)\frac 1 y \iff y \le 1.05x$

配合上前缀和，一段一段往前跳就好了。会跳多少次呢？y=1.05x，迭代一下，指数增长，所以分的段数是对数级别。这是一个时间复杂度 $O(n\lg n)$ 的算法。牺牲了一点时间，但显然可以保证相对误差不超过5%。常数会不会很大呢？ $\log_{1.05}10^5 \approx 236$ ，总运算量在千万级别，可接受。

有一些其他做法，比如前2000个暴力算，后面的把分母统统当作i-ai/2，的确可以AC，但是……总感觉不太科学？

【UER #7】天路一道和相对误差有关的好题。

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAX_N = 1e5;
const double r = 1.05;
double M[MAX_N+1], S[MAX_N+1];int main()
{int N;double a;scanf("%d %lf", &N, &a);for (int i = 1; i <= N; ++i)scanf("%lf", &M[i]);for (int i = 1; i <= N; ++i)S[i] = S[i-1] + M[i];for (int i = 1, j, k, p, q; i <= N; ++i) {double ans = 0;j = floor(i*a);while (j) {p = i-j;q = std::min((int)std::max(ceil(p*r), double(p+1)), i);k = i-q;ans += (S[j]-S[k])/p;j = k;}printf("%f\n", ans*M[i]);}return 0;
}