Keshawn_lu's Blog

PAT 1049.数列的片段和

数组
字数统计: 519阅读时长: 2 min
2021/02/13 Share

题目简介：

给定一个正数数列，我们可以从中截取任意的连续的几个数，称为片段。例如，给定数列 { 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。

输入格式：

输入第一行给出一个不超过 105 的正整数 N，表示数列中数的个数，第二行给出 N 个不超过 1.0 的正数，是数列中的数，其间以空格分隔。

输出格式：

在一行中输出该序列所有片段包含的数之和，精确到小数点后 2 位。

输入样例：

1
2
4
0.1 0.2 0.3 0.4

输出样例：

1
5.00

思路：

一开始想着用深搜+回溯的方法，但是很遗憾超时了。

所以想了想，感觉可以巧做这道题。

如0.1, 0.2, 0.3这个数列，有0.1的子数列占3个（即0.1为首元素的子数列）；然后计算有0.2存在的数列时，首先在之前3的基础上加上0.2为首元素的子数列，即3 + 2 = 5，然后把只有0.1的数列减去，最终的结果就为0.2存在的个数。

依次递推，就能得出结果

tip:

  • 这题对数据要求精度很高，得用long double才可以。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <cmath>
#include <iomanip>

using namespace std;


int main()
{
	int N;
	cin >> N;

	vector<double> nums(N);

	for (int i = 0; i < N; i++)
		cin >> nums[i];

	long double sum = 0;
	long double temp = 0;
	for (long i = N, j = 0; i >= 1; i--, j++) {

		temp += i;

		sum += temp * nums[j];

		temp = temp - (j + 1);
	}

	printf("%.2llf", sum);
}
CATALOG
  1. 1. 题目简介：
    1. 1.1. 输入格式：
    2. 1.2. 输出格式：
    3. 1.3. 输入样例：
    4. 1.4. 输出样例：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网