(python3)1049.数列的片段和(20分)

86 阅读 0 评论 57 点赞

我是靠谱客的博主听话小笼包，最近开发中收集的这篇文章主要介绍(python3)1049.数列的片段和(20分)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目赘述如下：

给定一个正数数列，我们可以从中截取任意的连续的几个数，称为片段。例如，给定数列{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⁵的正整数N，表示数列中数的个数，第二行给出N个不超过1.0的正数，是数列中的数，其间以空格分隔。

输出格式：

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

输入样例：

4
0.1 0.2 0.3 0.4

输出样例：

5.00

题目解析：

这是一道所有子列求和的问题，题意没问题，问题是解决思路。难道我们暴力循环求出每个子列的和并累加么？

下面先给出一个较为简洁的代码：

n = eval(input())
lst = list(map(float,input().split()))
sub = [0.0 for i in range(n)]
sub[0] = lst[0]
ans = sub[0]
for i in range(1,n):
sub[i] = sub[i-1] + lst[i]
ans += sub[i]
for j in range(i):
ans += sub[i] - sub[j]
print('%.2f'%ans)

从头开始的子列和存放在sub[]列表中，ans存放最终结果，双重循环第二层当前子列和减去前边的子列和求得从当前位置开始往后的子列的和。。。看似简洁一点，但是这仍然是个O(N^2)的方案，python语言这个方法后两个测试点超时，因此另辟思路。

求和的和还有什么思路呢？每个元素加了多少次一定是固定的。代码如下所示：

""""
0.1
0.2
0.3
0.4
0.1
0.3
0.6
1.0
0.2
0.5
0.9
0.3
0.7
0.4
"""
n = eval(input())
lst = list(map(float,input().split()))
ans = 0.0
for i in range(n):
ans += lst[i]*(i+1)*(n-i)
print('%.2f'%ans)

更简洁，而且是O(N)的方案。每个元素被加了多少次可自行分析一下（看注释分析）。