PAT甲级1104.

目录

A1104

题目

样例

输入:

4
0.1 0.2 0.3 0.4

输出:

5.00

思路和坑点

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开始,则对于第i个数字来说,首先考虑以第i个数开头的序列,这和第i个数后边的数字个数有关,显然以第i个数开头的序列有n-i个。然后考虑一共有多少个以i开头的序列组(单独开头的序列和包含的序列),这和i前边有多少个数字有关,显然一共有i+1组,故每一个数字出现的次数为(n-i)*(i+1)。由此,读入每一个数次计算并累加即可

AC代码

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<algorithm> 
#include<map>
#include<unordered_map>
#include<vector>
#include<queue> 
#include<string> 
using namespace std;   

int main(){    
#ifdef ONLINE_JUDGE    
#else    
    freopen("1.txt", "r", stdin);    
#endif    
    int n;
    double sum=0;
    cin>>n;
    for(int i=0;i<n;i++){
        double temp;
        cin>>temp;
        sum+=temp*(n-i)*(i+1);    //如果下标从0开始,对于第i个数,出现的次数为(n-i)*(i+1)次 
    }
    printf("%.2f",sum);
    return 0;    
}