自动搬运

查看原文

来自洛谷，原作者为

	xyz32768 “各方面相差太远”

搬运于2025-08-24 21:46:23，当前版本为作者最后更新于2017-09-24 21:04:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这道题我一直懵逼，后来看了题解中的一种玄学方法，看来我还是太弱。

这种玄学方法的要点就是利用“只要结果的相对误差不超过5%即可”这一条件。

首先，定义一个常数$T$，在$100$左右。

对于第$i$个行星，令$x=\lfloor a*i\rfloor$。可以看出，对第$i$个行星有贡献的是$[1,x]$范围内的行星。

当$x≤T$时，暴力统计。

当$x>T$时，把$[1,x]$分成$T$个长度尽可能平均的小区间（小区间过大会使误差变大）。

每一个小区间$[x,y]$的贡献的近似值就是$(M_i*\sum_{j=x}^yM_j)/(i-\frac{x+y}{2})$（取中点作为分母）

由于$0.01<a≤0.35$得到，这个近似值与准确值的相对误差不超过5%。

代码：

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
inline int read() {
    int res = 0; bool bo = 0; char c;
    while (((c = getchar()) < '0' || c > '9') && c != '-');
    if (c == '-') bo = 1; else res = c - 48;
    while ((c = getchar()) >= '0' && c <= '9')
        res = (res << 3) + (res << 1) + (c - 48);
    return bo ? ~res + 1 : res;
}
const double eps = 1e-8;
const int N = 1e5 + 5;
int n; double a, m[N], res[N], sum[N];
int main() {
    int i, j; n = read(); scanf("%lf", &a);
    for (i = 1; i <= n; i++) sum[i] = sum[i - 1] + (m[i] = read());
    for (i = 1; i <= n; i++) {
        int x = 1.0 * i * a + eps;
        if (!x) continue;
        if (x <= 100) for (j = 1; j <= x; j++)
            res[i] += m[i] * m[j] / (i - j);
        else {
            int tx = 1, ty, tz = x / 100, ta = x % 100;
            for (j = 1; j <= 100; j++) {
                ty = tx + tz - (j > ta);
                res[i] += (sum[ty] - sum[tx - 1]) * m[i] / (i - (tx + ty) / 2);
                tx = ty + 1;
            }
        }
    }
    for (i = 1; i <= n; i++) printf("%.6lf\n", res[i]);
    return 0;
}