我的PAT系列文章更新重心已移至Github，歡迎來看PAT題解的小伙伴請到Github Pages瀏覽最新內(nèi)容。此處文章目前已更新至與Github Pages同步。歡迎star我的repo。
題目
給定一個正數(shù)數(shù)列，我們可以從中截取任意的連續(xù)的幾個數(shù)，稱為片段。例如，給定數(shù)列 { 0.1, 0.2, 0.3, 0.4 }，我們有 (0.1) (0.1,
0.2) (0.1, 0.2, 0.3) (0.1, 0.2, 0.3, 0.4) (0.2) (0.2, 0.3) (0.2, 0.3, 0.4)
(0.3) (0.3, 0.4) (0.4) 這 10 個片段。
給定正整數(shù)數(shù)列，求出全部片段包含的所有的數(shù)之和。如本例中 10 個片段總和是 0.1 + 0.3 + 0.6 + 1.0 + 0.2 + 0.5 + 0.9
- 0.3 + 0.7 + 0.4 = 5.0。
輸入格式：
輸入第一行給出一個不超過 的正整數(shù)
，表示數(shù)列中數(shù)的個數(shù)，第二行給出
個不超過 1.0
的正數(shù)，是數(shù)列中的數(shù)，其間以空格分隔。
輸出格式：
在一行中輸出該序列所有片段包含的數(shù)之和，精確到小數(shù)點后 2 位。
輸入樣例：
4
0.1 0.2 0.3 0.4
輸出樣例：
5.00
思路
又是一道數(shù)學(xué)題。
解題的代碼很少，不過在下面的分析中還加入了浮點型數(shù)據(jù)精度的分析，雖然不是必要的。
-
先計算出數(shù)列中每一個元素在所有片段和中被包含的次數(shù)：
每一個包含a[i]的片段需要在a[i]左側(cè)（包含a[i]）和a[i]右側(cè)（也包含a[i]）各選取一個端點。我們使用0開始的計數(shù)。左側(cè)端點選取可能有i+1種，右側(cè)端點選取可能有N-i種。
因此包含a[i]的片段和一共有(i+1)(N-i)種，做一個加權(quán)求和即可求出片段和：
-
嚴(yán)謹(jǐn)起見的分析： 最大可能的片段和（我們要用的變量類型）：
令N=100000，任意i都有a[i]=1.0，此時的片段和為
這個數(shù)約等于1.67e14，題目要求精度達(dá)到小數(shù)點后2位，即相當(dāng)于相對誤差最多為6e-17。然后我們看一下不同浮點型(Wiki)的精度：
- 單精度浮點的誤差：尾數(shù)部分有23位，精度為1.2e-7；
- 雙精度浮點的誤差：尾數(shù)部分有52位，精度為2.2e-16；
- 擴(kuò)展精度的浮點型的誤差：尾數(shù)部分有63位，精度為1.1e-19；
可以看出單精度浮點是絕對不能用的，雖然雙精度浮點的誤差略大于上面分析的結(jié)果，但是我覺得PAT不會（事實上也沒有）挖這個坑，所以用
double類型的會過（我沒有試過float）。如果要寫更加嚴(yán)謹(jǐn)?shù)拇a，應(yīng)使用long double。 還有一個問題，看了這篇博客才發(fā)現(xiàn)，同樣是數(shù)據(jù)范圍的問題。
(i+1)(N-i)最大值約為N^2/4也就是2.5e9，32位有符號整型int的最大值是2^31-1，約為2e9，先乘這兩個整數(shù)可能會發(fā)生溢出。那篇博客說在求和時先算這兩個整數(shù)的乘積會有測試點過不去，就是測試點在測試N很大的情況。
代碼
最新代碼@github，歡迎交流
#include <stdio.h>
int main()
{
int N;
double ai, sum = 0;
scanf("%d", &N);
for(int i = 0; i < N; i++)
{
scanf("%lf", &ai);
/* ai is put at the beginning to avoid overflow */
sum += ai * (i + 1) * (N - i);
}
printf("%.2lf", sum);
return 0;
}
