题目

Given a sequence of positive numbers, a segment is defined to be a consecutive subsequence. For example, given the sequence {0.1, 0.2, 0.3, 0.4}, we have 10 segments: (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).

Now given a sequence, you are supposed to find the sum of all the numbers in all the segments. For the previous example, the sum of all the 10 segments is 0.1 + 0.3 + 0.6 + 1.0 + 0.2 + 0.5 + 0.9 + 0.3 + 0.7 + 0.4 =

5.0.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N, the size of the sequence which is no more than 105. The next line contains N positive numbers in the sequence, each no more than 1.0, separated by a space.

Output Specification:

For each test case, print in one line the sum of all the numbers in all the segments, accurate up to 2 decimal places.

Sample Input:

4

0.1 0.2 0.3 0.4

Sample Output:

5.00

题目分析

给定⼀个正数数列，从中截取任意连续的⼏个数，称为⽚段。例如，给定数列{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，在⼀⾏中输出该序列所有⽚段包含的数之和，精确到⼩数点后2位

解题思路

找到每个数字在所有序列中出现次数的规律：如果当前是第i个数，则总出现次数等于i*(n+1-i)
计算总和时，只需遍历i，总和+=当前数字i(n+1-i)

易错点

doubleintint和intintdouble，

t+=i*(n+1-i)*m;//int*int*double 本题中n取值最大为10^5，所以int*int之后还是int可能越界，测试点2,3错误

t+=m*(n+1-i)*i;//double*int*int 本题中n取值最大为10^5，但是double*int之后，结果隐式转换为double继续乘int，不会越界

Code

Code 01

#include <iostream>

using namespace std;

int main() {

	int n;

	cin >> n;

	double sum = 0.0, temp;

	for (int i = 1; i <= n; i++) {

		cin >> temp;

		sum = sum + temp * i * (n - i + 1);

	}

	printf("%.2f", sum);

	return 0;

}

Code 01

#include <iostream>

using namespace std;

int main(int argc,char * argv[]) {

	long long n;

	scanf("%d",&n);

	double m, t=0.0;

	for(long long i=1; i<=n; i++) {

		scanf("%lf",&m);

		t+=i*(n+1-i)*m; //如果i定义为int这样写，测试点2,3不通过，因为n最大取值为10^5，int*int越界

		//t+=m*i*(n+1-i);

	}

	printf("%.2f",t);

	return 0;

}

巴特西

PAT Advanced A1104 Sum of Number Segments (20) [数学问题]

题目

题目分析

解题思路

易错点

Code

Code 01

Code 01

最新文章

热门文章