有\(n\)个质量分别为\(m_i\)行星（\(n\leq 1e5\)）排成一排，给定一个很小的常数\(A\)，对于每一个行星\(i\)，求\(ans[i]\)=\(\Sigma_{j=1}^{A*i}(m_i*m_j/(i-j))\)，误差不超过5%即可算正确
乱搞。。。
假设\((i-j)\)是一个定值\(k\)，即\(k\)只由\(i\) 决定，那么维护一个前缀和\(s\),就有\(ans[i]=m_i*s[A*i]/k\)，可以\(O(1)\)完成
然而\((i-j)\)同时由\(i\)和\(j\)决定，于是就轮到乱搞上场了
由于题目说了\(A\)很小，所以\(A*i\)也应该很小，所以我们将\(i-1\)和\(i-A*i\)看得差不多，即将它们都看作是\(i-(A*i)/2\)，即上面的\(k\)，这样做在\(n\)较大的情况下可以满足误差较小，而\(n\)较小的情况暴力即可
Code:
#include<bits/stdc++.h> #define N 100005 using namespace std; int n,now=0; double a,m[N],s[N]; int main() { scanf("%d%lf",&n,&a); for(int i=1;i<=n;++i) scanf("%lf",m+i),s[i]=s[i-1]+m[i]; int p=min(2000,n); for(int i=1;i<=p;++i)//暴力 { double ans=0.0; for(int j=floor(i*a);j>=1;--j) ans+=m[i]*m[j]/(i-j); printf("%lf\n",ans); } for(int i=p+1;i<=n;++i) printf("%lf\n",m[i]*s[(int)floor(i*a)]/(i-(i*a)/2)); return 0; }转载于:https://www.cnblogs.com/Chtholly/p/11420964.html
相关资源：JAVA上百实例源码以及开源项目