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
3
5
6
2
4
Sample Output
0.000000
0.000000
0.000000
1.968750
2.976000
0.000000
0.000000
1.968750
2.976000
HINT
精确结果应该为0 0 0 2 3,但样例输出的结果误差不超过5%,也算对。
分析
乍一看这似乎是一道不可做题…… $O(\alpha N^2)$的复杂度，大概再怎么卡常数也是过不了吧？别急……我们看一下这句话……“答案误差不超过5%即可”。瞬间变水题啊好吗……
考虑到j-i足够大时相邻一定范围内的$\frac{1}{j-i}$相差很小，我们可以随便选一个i来计算j-i，把它作为分母计算一定范围内的i星球对j产生的合力。
具体地，我们可以随便计算出一个需要精确计算的范围$\delta$，对距离大于这个范围的星球统一计算合力即可。
#include <cctype>
#include <cstdio>
#include <cmath>
#include <cstdlib>
template<typename T>inline ;
, c = getchar();
x = c - + c - }
;
;
freopen( freopen( getd(N);
scanf( / A;
S[] = ;
;i <= N;++i)
scanf(] + M[i];
printf();
;i <= N;++i){
Ans = ;
t = ( s = ( ){
mid = () * (i-s+));
Ans += M[i] * S[s-] / mid;
}
;
Ans += M[i] * M[j] / (i - j);
printf( }
;
}
#include <cstdio>
#include <cmath>
#include <cstdlib>
template<typename T>inline ;
, c = getchar();
x = c - + c - }
;
;
freopen( freopen( getd(N);
scanf( / A;
S[] = ;
;i <= N;++i)
scanf(] + M[i];
printf();
;i <= N;++i){
Ans = ;
t = ( s = ( ){
mid = () * (i-s+));
Ans += M[i] * S[s-] / mid;
}
;
Ans += M[i] * M[j] / (i - j);
printf( }
;
}
数值近似