【PAT甲级 - C++题解】1104 Sum of Number Segments

1104 Sum of Number Segments

Given a sequence of positive numbers, a segment is defined to be a consecutive subsequence. For example, given the sequence { 0.1, 0.2, 0.3, 0.4 }, we have 10 segments: (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) and (0.4).

Now given a sequence, you are supposed to find the sum of all the numbers in all the segments. For the previous example, the sum of all the 10 segments is 0.1 + 0.3 + 0.6 + 1.0 + 0.2 + 0.5 + 0.9 + 0.3 + 0.7 + 0.4 = 5.0.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N, the size of the sequence which is no more than 105. The next line contains N positive numbers in the sequence, each no more than 1.0, separated by a space.

Output Specification:

For each test case, print in one line the sum of all the numbers in all the segments, accurate up to 2 decimal places.

Sample Input:

4
0.1 0.2 0.3 0.4

Sample Output:

5.00

题意

给定一个正数序列，每个非空连续子序列都可被称作一个数段。

例如，给定序列 { 0.1, 0.2, 0.3, 0.4 }，该序列共包含 10 个不同数段，(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 个数段的总和为 0.1 + 0.3 + 0.6 + 1.0 + 0.2 + 0.5 + 0.9 + 0.3 + 0.7 + 0.4 = 5.0。

思路

我们可以假设当前要算的是第 i 个数：

那么在 0 ~ i 之间包含 i 的连续子字段有 i 个，而在 i ~ n 之间包含 i 的连续子字段有 n - i + 1 个。

所以只用将两部分拼起来就可以得到在 0 ~ n 之间包含 i 的连续子字段数量，即一共 i * (n - i + 1) 个。故我们可以从前往后依次计算每个数的总值，即得到 a[i] * i * (n - i + 1) 。

注意，答案输出保留 2 位小数，并且要用 long double 去存储数值，double 的精度不够。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N];
int main()
{
    int n;
    cin >> n;
    long double res = 0;
    for (int i = 1; i <= n; i++)
    {
        long double x;
        cin >> x;
        res += x * i * (n - i + 1);
    }
    printf("%.2Lf\n", res);
    return 0;
}