PAT A1104 Sum of Number Segments(C++)

发表于 | 分类于 | |
字数统计: 250 字 | 阅读时长 ≈ 1 分钟
PAT甲级目录 | PAT乙级目录

题目描述

原题地址：A1104 Sum of Number Segments
中文版：B1049 数列的片段和

解题思路

找规律，关键是求数列中每个数出现的次数。因为片段是连续的，对于第 $i$ 个（$i$ 从 1 开始）数所在的片段，片段起点可以是该数左边（包括 $i$ ）的任意一个数，即有 $i$ 种可能；片段终点可以是该数右边（包括 $i$ ）的任意一个数，即有 $n - i + 1$ 种可能。所以包含 $i$ 的片段总共有 $i * (n - i + 1)$ 种可能。
相似的题目： PAT-B1040-有几个PAT(C++)

易错点

  • ans += x * i * (n - i + 1);
    • 将 x 放在第一个位置，乘积将自动转换为浮点数再累加，保证了精度

代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
#include <cstdio>
int main() {
  int n;
  double x, ans = 0;
  scanf("%d", &n);
  for(int i = 1; i <= n; i++){
    scanf("%lf", &x);
    ans += x * i * (n - i + 1);
  }
  printf("%.2lf", ans);
  return 0;
}