OI技术宅

Tech Otakus save the world!
Welcome,my dear friends!
【I'm kiana/kiana810@126.com】

【HNOI2008】遥远的行星

【题目描述】

直线上有 n 颗行星,x=i 处有行星 i。行星 j 受到行星 i 的作用力,当且仅当i<=αj,此时 j 受作用力的大小为: 

其中α为很小的常量,故直观上说,每颗行星都只受距离遥远的行星的作用。请计算每颗行星的受力。

【输入】

第一行两个整数n和α,接下来n行输入n个行星的质量mi。

【输出】

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

【输入样例】

5 0.3
3
5
6
2
4

【输出样例】

0.000000
0.000000
0.000000
1.968750
2.976000

【数据范围】

1<=n<=10^5

0<=mi<=10^7

【题解】

先写出朴素的算式:


稍作变形可得:


但这样是O(n^2)的,时间上过不了,所以我们考虑暴力计算一部分,再由暴力的这部分推出剩下的部分。假设暴力的部分为T,化简下面这个算式:




经过神一样的目测+乱搞,均摊下来可得:



这样F[i+T]可以在O(α*T)内算出,总时间复杂度就降为O(n*αT)。

由于精度要求较低,所以P党取T=100就可以过,而C++要取T=800以上。

【代码】

治好了多年的公式恐惧症。。

http://paste.ubuntu.com/8511907/

评论

© OI技术宅 | Powered by LOFTER