首页 > 代码库 > 【bzoj1011】[HNOI2008]遥远的行星

【bzoj1011】[HNOI2008]遥远的行星

2024-08-12 23:22:28   218人阅读

1011: [HNOI2008]遥远的行星

Time Limit: 10 Sec  Memory Limit: 162 MBSec  Special Judge
Submit: 3711  Solved: 1375
[Submit][Status][Discuss]

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%,也算对

 

 

【吐槽】

省选居然会考这么坑的题。。。

“只要结果的相对误差不超过5%即可”这是关键的一句话。

因为当行星的相距很远时，作用力会非常小，完全可以估算，即把前1-now的行星到当前行星的距离都算做到now/2的距离，O(1)求解。（这算是一种贪心策略吗？）

如何提高智商？？？这是个永恒的话题

 

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<cstdlib> 6 #include<ctime> 7 #include<algorithm> 8 using namespace std; 9 #define MAXN 10001010 #define eps 1e-811 int n;12 double A,m[MAXN],sum[MAXN],ans[MAXN];13 inline int read()14 {15     int x=0,f=1;  char ch=getchar();16     while(!isdigit(ch))  {if(ch==‘-‘)  f=-1;  ch=getchar();}17     while(isdigit(ch))  {x=x*10+ch-‘0‘;  ch=getchar();}18     return x*f;19 }20 int main()21 {22     n=read();  scanf("%lf",&A);  sum[0]=0.000000;23     for(int i=1;i<=n;i++)  {scanf("%lf",&m[i]);  sum[i]=sum[i-1]+m[i];}24     for(int i=1;i<=min(2000,n);i++)25     {26         int r=eps+floor(A*i);27         for(int j=1;j<=r;j++)  ans[i]+=m[i]*m[j]/(i-j);28     }29     for(int i=2001;i<=n;i++)30     {31         int r=eps+floor(A*i);32         ans[i]+=sum[r]*m[i]/(double)(i-(int)r/2);33     }34     for(int i=1;i<=n;i++)  printf("%6lf\n",ans[i]);35     return 0;36 }

 

 

【bzoj1011】[HNOI2008]遥远的行星


联系
我们