BZOJ1011 [HNOI2008]遙遠的行星 【奇技淫巧】

1011: [HNOI2008]遙遠的行星

Time Limit: 10 Sec   Memory Limit: 162 MBSec   Special Judge

Submit: 5058   Solved: 1888

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

這題的正解也着實讓我吓跪。。。

首先對于i，ansi = ∑M[i] * M[j]/(i - j)

直接模拟O(a n^2)鐵定T

我們觀察題目，樣例為何不直接輸出整數呢？5%這個誤差為何如此之大？

是不是在暗示着我們什麼？

對，我們不一定要如此嚴謹地求解

當i足夠大時，i - j對于結果的影響就變小了，我們隻需大概用個0.5 * a * i來替代j就降一維的複雜度

注意當i比較小時還是要規規矩矩地算

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define fo(i,x,y) for (int i = (x); i <= (y); i++)
#define Redge(u) for (int k = head[u]; k != -1; k = edge[k].next)
using namespace std;
const int maxn = 100005,maxm = 100005,INF = 1000000000;
inline int read(){
	int out = 0,flag = 1;char c = getchar();
	while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}
	while (c >= 48 && c <= 57) {out = out * 10 + c - 48; c = getchar();}
	return out * flag;
}
double ans,a,M[maxn],sum[maxn];
int n,t;
int main()
{
	n = read(); cin>>a;
	REP(i,n) scanf("%lf",&M[i]),sum[i] += sum[i - 1] + M[i];
	REP(i,n){
		t = (int)floor(i * a + 1e-8); ans = 0;
		if (i <= 1000){
			REP(j,t) ans += M[i] * M[j] / (i - j);
			printf("%.6lf\n",ans);
		}
		else printf("%.6lf\n",M[i] * sum[t] / (i - t / 2));
	}
	return 0;
}
           

轉載于:https://www.cnblogs.com/Mychael/p/8282801.html