程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> BZOJ 1011: [HNOI2008]遙遠的行星

BZOJ 1011: [HNOI2008]遙遠的行星

編輯:C++入門知識

BZOJ 1011: [HNOI2008]遙遠的行星


 

n大於一定的范圍後,取近似值

 

1011: [HNOI2008]遙遠的行星

Time Limit: 10 Sec Memory Limit: 162 MBSec Special Judge
Submit: 2350 Solved: 837
[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%,也算對

 

Source


 

 

#include 
#include 
#include 
#include 
#include 

using namespace std;

const int maxn=100100;
const double eps=1e-8;

int n;
double a;
double m[maxn]; 
double pre[maxn];
double ans[maxn];

int main() {


	scanf("%d%lf",&n,&a);

	for(int i=1;i<=n;i++){
		scanf("%lf",m+i);
		pre[i]=pre[i-1]+m[i];
	}

	ans[1]=0;
	int now=0;
	for(int i=2;i<=min(2000,n);i++){
		while((double)i*a+eps>=(double)(now+1)) now++;
		for(int j=1;j<=now;j++){
			ans[i]+=m[i]*m[j]/(double)(i-j);
		}
	}

	for(int i=2001;i<=n;i++){
		while((double)i*a+eps>=(double)(now+1)) now++;
		ans[i]=pre[now]*m[i]/(double)(i-(int)now/2);
	}

	for(int i=1;i<=n;i++){
		printf("%.8f\n",ans[i]);
	}

	return 0;
}


 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved