LightOJ1234 Harmonic Number —— 分区打表

题目链接：https://vjudge.net/problem/LightOJ-1234

1234 - Harmonic Number

PDF (English)

Statistics

Forum

Time Limit: 3 second(s)

Memory Limit: 32 MB

In mathematics, the n harmonic number is the sum of the reciprocals of the first n natural numbers:

In this problem, you are given n, you have to find H.

Input

Input starts with an integer T (≤ 10000), denoting the number of test cases.

Each case starts with a line containing an integer n (1 ≤ n ≤ 10).

Output

For each case, print the case number and the n harmonic number. Errors less than 10 will be ignored.

Sample Input	Output for Sample Input
12 1 2 3 4 5 6 7 8 9 90000000 99999999 100000000	Case 1: 1 Case 2: 1.5 Case 3: 1.8333333333 Case 4: 2.0833333333 Case 5: 2.2833333333 Case 6: 2.450 Case 7: 2.5928571429 Case 8: 2.7178571429 Case 9: 2.8289682540 Case 10: 18.8925358988 Case 11: 18.9978964039 Case 12: 18.9978964139

题意：

对于一个数n，输出 sigma(1/k)，1<=k<=n。

题解：

1.一开始想离线做，结果发现输入完一个测试数据就必须输出，不能离线。

2. 由于n<=1e8，开一个1e8大小的数组是不可能的，那么可以尝试开一个1e6的数组，然后每隔100就存一个数据，分区打表。

3.假设能开1e8大小的数组，那么经过预处理后，那么查询只需O(1)，这种处理方式是完全偏向于时间；如果不开数组，每次都重新计算，那么每次查询需O（n），而n可高达1e7，这种处理方式完全偏向于空间。可见两种极端的处理方式都无法解决问题，而需在这两者之间作个权衡，人生也如此！

代码如下：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <vector>

 #include <cmath>

 #include <queue>

 #include <stack>

 #include <map>

 #include <string>

 #include <set>

 using namespace std;

 typedef long long LL;

 const int INF = 2e9;

 const LL LNF = 9e18;

 const int mod = 1e9+;

 const int MAXM = 1e5+;

 const int MAXN = 1e6+;

 double table[MAXN];

 void init()

 {

     double s = ;

     for(int i = ; i<=; i++)

     {

         s += 1.0/i;

         if(i%==) table[i/] = s;

     }

 }

 int main()

 {

     init();

     int T, n, kase = ;

     scanf("%d", &T);

     while(T--)

     {

         scanf("%d", &n);

         double s = table[n/];

         for(int i = n/*+; i<=n; i++)

             s += 1.0/i;

         printf("Case %d: %.10f\n", ++kase, s);

     }

 }