Home PAT 1104 Sum of Number Segments
Post
Cancel

PAT 1104 Sum of Number Segments

题解

Link

思路很简单, 就不说了, 主要是浮点数溢出和精度的问题.

两个坑点:

  1. double 存储答案会溢出, 过不了测试点 2、3. 应该用 long d📧ouble 或者 long long.
  2. 如果是用 long double, 那么一定要是 ans+=a*i*(n-i+1), 而不是 ans+=i*(n-i+1)*a; 如果用 long long, 那么一定要是 ans+=(long long)(a*1000)*i*(n-i+1) (注意强制类型转换 (long long) 要加上, 不然测试点 2 过不了). 也就是说, a 一定要是第一个, 不能放在 i*(n-i+1) 后面, 不然就是会挂测试点 2.

总之就是, 浮点数相乘的顺序影响结果精度!

后来我仔细思考了一下, C++ 乘法的运算顺序是从左至右的. 也就是说, 如果是 a*i*(n-i+1), 那么就是先计算 a*i, 这个结果由于 along double 所以也是 long double; 再乘以 (n-i+1), 这个结果由于 a*ilong double 所以也是 long double. 因此最后的结果是以 long double 的 12 个字节长度存储的.

相反地, 如果先计算 i*(n-i+1), 那么 i*(n-i+1) 的结果是以 int 类型存储的, 占 4 个字节; 然后乘以 long double 后, 会因为长度扩展出现问题 (以上纯属我的个人想法, 若有不对请指出 📮 by email 📧).

long double 版:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <cmath>
using namespace std;
#define double long double //就这么写!
int n;
double a,ans;
int main() {
    cin>>n;
    for(int i=1;i<=n;++i){
        scanf("%Lf",&a);
        ans+=a*i*(n-i+1);
    }
    printf("%.2Lf\n",ans);
    return 0;
}

long long 版 (注意是要乘以 1000! 因为是保留两位小数):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <cmath>
using namespace std;
int n;
double a;
long long ans;
int main() {
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>a;
        ans+=(long long)(a*1000)*i*(n-i+1);
    }
    printf("%.2f\n",ans/1000.0);
    return 0;
}

long double

doublelong double 的比较:

  • double 占 8 字节,long double 占 12 字节, 内存差得不算多.
  • double 只能精确到小数点后 15 位, 但 long double 能精确到 18 位左右.

宏定义: 在程序开头宏定义 #define double long double 输入: scanf("%Lf", &a); 输出: printf("%.10Lf", a); 函数: long double 的常用函数都要在末尾加个 l, 如: fabsl(a), sqrtl(a), cosl(a)

运算顺序

看下面这段示例代码 (与本题无关, 但是错得如出一辙):

1
2
3
4
5
6
7
8
9
int x = -2147483647;
long long t;

// 这句话会报错
t = x * -1;

// 改成这样就好了
t = x;
t *= -1;

真正的运算顺序是 x 先乘以 -1, 把值赋给 x, 再把 x 的值赋给 t.

但是 xint 型的, x 乘以 -1 就会超出 int 上限, 所以报错.

This post is licensed under CC BY 4.0 by the author.