当前位置: 代码迷 >> 综合 >> PAT 1049 数列的片段和 (20 分) 测试点2
  详细解决方案

PAT 1049 数列的片段和 (20 分) 测试点2

热度:57   发布时间:2023-11-24 12:11:09.0

题目传送门<==戳这

总共n个元素,对于第 i 个输入的temp:

1.以temp为起点的片段有:n - i + 1 个。并且这些片段都含有temp,即有:(n-i+1)个 temp

2.起点小于 temp 并且经过temp的片段有 i -1 个:即以1,2 ,3…i-1 为起点,这些片段从temp这个元素开始相当于就是情况1,只是在情况1的条件下加上了temp以前的元素(这里如果不明白需要反复琢磨并自己动手画一画)
即相当于有 i - 1 个情况1的片段,也就是有 ( i - 1 ) * (n - i + 1)个temp

两种情况相加,最终得出有 i * ( n - i + 1) 个temp,而所有子片段的元素和等于 :( x 元素的个数 * x 元素值 )的和

如果能读到这里,那离解决这道题不远了

还有一个要注意的是,如果在计算及内部有数量过多的浮点型操作会使答案出现比较大的偏差,因此为了减少这种误差,我们先将输入的temp乘以1000,求和之后再除以1000,这样可以有效减小误差。

上代码帮助理解:

#include <iostream>
#include <cstdio>
using namespace std;
int main(){
    int n;long long ans=0;double temp;cin>>n;for(int i=1;i<=n;i++){
    cin>>temp;ans+=(long long)(temp*1000)*i*(n-i+1);   ==>这里务必强制转换成long long,因为给ans赋值要匹配ans的数据类型}printf("%.2f",1.0*ans/1000);
}