PAT Basic 1049. 数列的片段和

1. 题目描述：

给定一个正数数列，我们可以从中截取任意的连续的几个数，称为片段。例如，给定数列 { 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 个片段。

给定正整数数列，求出全部片段包含的所有的数之和。如本例中 10 个片段总和是 0.1 + 0.3 + 0.6 + 1.0 + 0.2 + 0.5 + 0.9 + 0.3 + 0.7 + 0.4 = 5.0。

2. 输入格式：

输入第一行给出一个不超过 \(10^5\) 的正整数 \(N\)，表示数列中数的个数，第二行给出 \(N\) 个不超过 1.0 的正数，是数列中的数，其间以一个空格分隔。

3. 输出格式：

在一行中输出该序列所有片段包含的数之和，精确到小数点后 2 位。

4. 输入样例：

4
0.1 0.2 0.3 0.4

5. 输出样例：

5.00

6. 性能要求：

Code Size Limit
16 KB
Java (javac)
Time Limit
500 ms
Memory Limit
128 MB
Other Compilers
Time Limit
200 ms
Memory Limit
64 MB

思路：

只能说Google的题就是nb。。。前面的题一直不涉及浮点型，我这里开始读入double类型值时都忘了用"%lf"了。。。

根据输入样例 { 0.1, 0.2, 0.3, 0.4 }：

可以找出规律：\(sum = \sum_{i=0}^{n-1} (i+1)*(n-i)*a_i\)，其中\(n\)为数列中数的个数，\(a_i\)表示数列中第\(i\)个数。

得出规律后我以为AC了。。。结果第一次提交testpoint2，3报wrong answer，检查了逻辑没有问题，无奈只能参考大佬的题解：PAT-Basic-1049. 数列的片段和 – Lnyan's Blog (llonely.com)

得知是类型转换造成的精度问题，更改了代码后，testpoint2依然过不了。应该是测试用例已经变了，然后又找到一个大佬的题解：1049. 数列的片段和(20)-浙大PAT乙级真题_浙大柳婼_柳婼的博客-CSDN博客

这里的bug点就是当数列中数的个数比较多时，double类型精度有限，多次累加会导致较大误差。所以需要把double类型值扩大1000倍转为long long类型，这样累加出一个精确值，最后输出时再除以1000.0转为浮点型，相当于做了一个scale，改过来之后终于AC。

My Code:

// #include <stdio.h>
// #include <stdlib.h> // malloc header

// // first submit testpoint2, 3 wrong answer
// int main(void)
// {
//     int numSize = 0;
//     double *pDouble = NULL;
//     int i=0;
//     double res = 0.0;
    
//     scanf("%d", &numSize);
    
// //     if(!numSize) // no input
// //     {
// //         printf("0.00");
// //         return 0;
// //     }
    
//     pDouble = (double *)malloc(sizeof(double) * numSize);
    
//     for(i=0; i<numSize; ++i)
//     {
// //         scanf("%f", pDouble+i); //wrong input for double
//         scanf("%lf", pDouble+i);
//         //printf("%.1f ", pDouble[i]);
// //         res += (i+1)*(numSize-i)*pDouble[i];
// //         res += (double)(i+1)*(double)(numSize-i)*pDouble[i];
//          res += pDouble[i]*(i+1)*(numSize-i);
//     }
    
//     printf("%.2lf", res);
    
//     free(pDouble);
//     return 0;
// }

// // testpoint2 still wrong answer
// #include <stdio.h>
// int main(void)
// {
//     int numSize = 0, i=0;
//     double res = 0.0, temp = 0.0;   
//     scanf("%d", &numSize);    
//     for(i=0; i<numSize; ++i)
//     {
//         scanf("%lf", &temp);
//         res += temp*(i+1)*(numSize-i);
//     } 
//     printf("%.2lf", res);
//     return 0;
// }

// AC refer to: https://blog.csdn.net/liuchuo/article/details/51994905
#include <stdio.h>
int main(void)
{
    int numSize = 0, i=0;
    double temp = 0.0;
    long long res = 0;
    
    scanf("%d", &numSize);    
    for(i=0; i<numSize; ++i)
    {
        scanf("%lf", &temp);
        res += (long long)(temp*1000)*(i+1)*(numSize-i);
        //res += temp*(i+1)*(numSize-i);
    } 
    printf("%.2lf", res/1000.0);
    return 0;
}