【bzoj1011】[HNOI2008]遥远的行星

2015.04.21 09:04 Tue | 22次阅读 | 旧日oi | 固定链接 | 源码

Description

直线上N颗行星,X=i处有行星i,行星J受到行星I的作用力,当且仅当i<=AJ.此时J受到作用力的大小为 Fi->j=Mi*Mj/(j-i) 其中A为很小的常量,故直观上说每颗行星都只受到距离遥远的行星的作用。请计算每颗行星的受力,只要结果的相对误差不超过5%即可.

Input

第一行两个整数N和A. 1<=N<=10^5.0.01< a < =0.35
接下来N行输入N个行星的质量Mi,保证0<=Mi<=10^7

Output

N行,依次输出各行星的受力情况

Sample Input

5 0.3
3
5
6
2
4

Sample Output

0.000000
0.000000
0.000000
1.968750
2.976000

HINT

精确结果应该为0 0 0 2 3,但样例输出的结果误差不超过5%,也算对

题解

很有意思的一道题。
如果要求精确解的话可能只有n^2的算法,但是因为它可以有误差,所以在用公式计算的时候我们可以把某连续的一段除数(j-i)变成一个值,至于这段多长,可以试一试,2000,,1000,100,50在bz上都能过。别的就没什么好说的了
公式:

我的程序

#include <bits/stdc++.h>
using namespace std;
int n;
double a;
double m[100005],f[100005];
int g[100005];
int main()
{
    //freopen("1011.in","r",stdin);
    cin>>n>>a;
    for(int i=1;i<=n;i++)
    {
        scanf("%lf",&m[i]);
        g[i]=floor(i*a);//g[i]:离i最近的需要计算的行星
    }
    for(int i=1;i<=min(n,50);i++)
        for(int j=1;j<=g[i];j++)
            f[i]+=m[i]*m[j]/(i-j);//预处理出前一段
    for(int i=51;i<=n;i++)
    {
        f[i]=m[i]*f[i-50]/m[i-50]*(i-50-g[i-50]/2)/(i-g[i-50]/2);//从f[i-50]递推一部分
        for(int j=g[i-50]+1;j<=g[i];j++) f[i]+=m[i]*m[j]/(i-j);//再独立计算一部分
    }
    for(int i=1;i<=n;i++)
        printf("%lf\n",f[i]);
}```