PAT乙级-1049. 数列的片段和(20)-详解+代码题目：PAT乙级-1049. 数列的片段和(20)

63 阅读 0 评论 42 点赞

我是靠谱客的博主魁梧白云，最近开发中收集的这篇文章主要介绍PAT乙级-1049. 数列的片段和(20)-详解+代码题目：PAT乙级-1049. 数列的片段和(20)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目：PAT乙级-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

思路：

我以为这道题的重点在于找规律求和，当我找到规律提交好的时候才发现，还是我太年轻，曹鹏博士怎么会找不出规律呢，他就是想让你找规律找晕了后兴高采烈地提交发现测试点2和测试点3错位。

1、首先来看一下规律吧，对于题中给的数列，首先遍历肯定是不可能的，要找一个规律。

①、给定n个元素的数列里的第i个元素，其左边有（i-1）个元素，右边有（n-i）个元素，因为自身也成一个元素，则可以说是（n-i+1）个元素。

②、左边的元素每一个都可以和右边的连续，即有（i-1）*（n-i+1）个元素，再加上自身和右侧的（n-i+1）个元素连续，即有（i-1）*（n-i+1）+（n-i+1）=i*（n-i+1）个元素。

③、对于数组的元素计数为（i-1），则将i=i+1带入得每个元素出现的次数是（n-i）*（i+1）

2、当做完了这些之后兴冲冲想提交时，曹鹏博士出现了，他会用测试点2和测试点3无情的告诉你，int会溢出哦：因为共有100000个数据，则最大的出现次数是50000*50001，这使得int溢出了，因此出现次数这个变量还得用double存。‘

3、当我把这个bug改掉以后，提交，发现测试点3还是通不过，仔细一想，能改的也就只有对小数的存储了，题目中根本没有声明小数的位数，为了节约空间和时间我就直接用float存储了，我把它改成double就神奇的通过了。呵，还有这种操作，你题目里也没写你小数点后的位数呀，谁知道能有小数点后7位以上？皮这一下你开心不？

#include<stdio.h>
#define N 100000
int main()
{
int i;
double a[N];
double sum = 0,appear,num;
scanf("%lf", &num);
for (i = 0; i < num; i++)
{
scanf("%lf", &a[i]);
appear = (num - i)*(i + 1);
sum += appear * a[i];
}
printf("%.2f", sum);
return 0;
}