PAT-A-1104 Sum of Number Segments (20)

题目

题目链接 数字段的总和 ## Description 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) (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. ## 题目描述 给定一系列整数,将一个 段(segment) 定义为连续的子序列。例如,给定序列{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。 ## 输入 每个输入包括一个测试用例。对于每个测试用例,第一行给出一个正整数N,表示序列的大小。下一行是这个序列的N个正整数,每个都不超过1.0,由空格隔开。 ## 输出 对于每个测试用例,在一行中输出所有的段的所有数字的和。保留两位小数。 # 解题 ## 思路分析 这个题只需要计算出每个位置的数字出现多少次,即可直接求出结果。

对于第i位上出现的数,以他开头的序列共N-i+1个。

以0.2为例,共(0.2) (0.2, 0.3) (0.2, 0.3, 0.4)。共4-2+1=3个。

但是包含上述三个序列的序列共i个,以0.2为例,除了上述的三个,还有以0.1开头的三个序列。即(0.1, 0.2) (0.1, 0.2, 0.3) (0.1, 0.2, 0.3, 0.4)。

同理0.3类似,(0.3) (0.3, 0.4)。除了这两个,包含这两个序列的序列有: (0.1, 0.2, 0.3) (0.1, 0.2, 0.3, 0.4)还有(0.2, 0.3) (0.2, 0.3, 0.4)。

Tips

找出数学规律,比直接模拟求出所有的序列再求和要方便得多。 ## 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
#pragma warning(disable:4996)
using namespace std;

int N;
double num[100001], sum = 0.0;
void solution()
{
cin >> N;
for (int i = 1; i <= N; i++)
{
cin >> num[i];
sum += num[i] * i * (N - i + 1);
}
printf("%.2f", sum);
}

int main()
{
freopen("1.txt", "r", stdin);
solution();
system("pause");
return 0;
}

测试数据

1
2
3
4
5
6
7
Sample Input:

4
0.1 0.2 0.3 0.4
Sample Output:

5.00