PAT乙级1049 || 数列的片段和（详解，C/C++示例，测试点分析）

Posted on In

数列的片段和

题目描述

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

输入格式

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

输出格式

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

输入样例

1
2
4
0.1 0.2 0.3 0.4

输出样例

1
5.00

问题解决

解题思想

初看此题时，我自然而然的想到了下面的代码1，但是提交时测试点2错误，为此我反复审题看看自己是不是漏掉了特殊情况，无果后又去大佬博客搜寻，最终没能解决，网上的解决方案大多是下面的代码2的思想。有大佬说可能代码1的方法精度有问题，但是到底是什么样的问题始终没能解决，如果有大佬明白，望告知，感激不尽。

当然本题也可采用暴力解法，不过超时是必然的。

代码1的思想

先累加包含第一个数的所有连续片段的和（sum0），例如，给定数列 { 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) ；接着以sum0为基础，累加上其减去一定个数个的相应数，例如，按上面的给定数列，第一次累加上：(0.2) (0.2, 0.3) (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) 减去4个0.1；第二次累加上： (0.3) (0.3, 0.4) ，相当于(0.2) (0.2, 0.3) (0.2, 0.3, 0.4)减去3个0.2；第三次累加上：(0.4)，相当于 (0.3) (0.3, 0.4)减去2个0.3；第四次累加上：0，相当于(0.4)减去1个0.4。其实明白了上面的规律，本题就很简单了。

代码2的思想

代码2也是对规律的应用，例如（左右滑动以查看全部内容）：

1
2
3
4
给定数列{a}，sum为：a
给定数列{a, b}，sum为：2*a + 2*b
给定数列{a, b, c}，sum为：3*a + 4*b + 3*c
给定数列{a, b, c, d}，sum为：4*a + 6*b + 6*c + 4*d

其实，给定包含 n 个正数的数列，sum为数列中所有的数乘上一定系数的累加，对于数列中任意一个数 a ，它的系数为 (i + 1) a (n - i)，其中i为 a 的次序，从0开始。

坑点提醒

注意：在代码2中sum累加的每一项不要写成：(n - i) (i + 1) a，而要写成： (i + 1) a (n - i)或者写成：a (double)(n - i) (double)(i + 1)或者写成：a (n - i) (i + 1)，因为(n - i) (i + 1) a会使得前面两个int型的数相乘，这可能会造成溢出，会导致测试点2 3错误。注意这几种写法的差别。

代码示例（C/C++）

代码1（测试点2答案错误）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <cstdio>
using namespace std;
const int maxn = 100001;
int main()
{
    int n;
    double a[maxn],sum0 = 0,sum1 = 0;
    scanf("%d",&n);
    for(int i = 0; i < n; i++){
        scanf("%lf",&a[i]);
        sum0 += a[i];  //sum0为n个正数的和
        sum1 += sum0;   //sum1为包含a[0]的所有连续片段的和
    }
    double sum2 = sum1;   //sum2为该序列所有片段包含的数之和
    for(int i = n; i >= 1; i--){
        sum1 -= i * a[n - i];
        sum2 += sum1;
    }
    printf("%.2lf",sum2);
    return 0;
}

代码2（全部通过）

1
2
3
4
5
6
7
8
9
10
11
12
#include <cstdio>
int main (void){
    int n;
    scanf("%d",&n);
    double temp,sum = 0;
    for (int i = 0; i < n; i++){
        scanf("%lf",&temp);
        sum += (i + 1) * temp * (n - i);
    }
    printf("%.2lf\n", sum);
    return 0;
}

题目来源：PAT乙级1049
作者：CAO, Peng
单位：Google

稀罕作者