PAT_A1104
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;
}