这道题为什么不能用前缀和来做呢，大佬们为什么会想到浮点数

YYAN_ZU @ 2024-05-06 19:56:41

#include<iostream>
using namespace std;
const int N=1010;
double a[N],sum[N];
int main()
{
    int k,i;
    cin>>k;
    for(i=1;;i++)
    {
        a[i]=1.0/i;
        sum[i]=sum[i-1]+a[i];
        if(sum[i]>k)
          break;
    }
    cout<<i;
    return 0;
}

by chenzait @ 2024-05-06 20:09:31

@YYAN_ZU 这道题怎么前缀和？，1/n肯定是浮点数啊如果 n≥2

前缀和是比如说问你从第一个数到最后一个数，问你从 a_l 到 a_r 反复问的情况下大大减少时间复杂度 这里假设sum为前缀和数组，每次询问输出

by Luke_li @ 2024-05-06 20:10:13

这和前缀和没关系。前缀和用于求一段区间的总和，这道题只是要求前n个数字的和 @YYAN_ZU

by zhouzihang1 @ 2024-05-06 20:13:03

@YYAN_ZU 可以，但不建议，经测试，你的数组大小需要开到 7.5 \times 10 ^ 5 才可以通过此题。

by YYAN_ZU @ 2024-05-06 22:44:50

@chenzait 因为我一看到这个sn的形式脑袋里就出现了a{i}=1/i,所以就想到了前缀和，然后就是S[I]=S[I-1]+A[I]来进行前缀和的处理

by YYAN_ZU @ 2024-05-06 22:46:01

@Luke_li 我当时想的是这前n个数字的和也可以看成是从1一直到第n个数的前缀和

by YYAN_ZU @ 2024-05-06 22:47:03

@zhouzihang1 我才发现按照我的思路来看的话，如果数组开的不是很大的话，程序AC

by YYAN_ZU @ 2024-05-06 22:51:05

@chenzait 大佬我还想问问，为什么1/n你就会想到浮点数呢，是因为这样的除法会有“除不尽”这个可能吗？所以你才会想到浮点数？

by Luke_li @ 2024-05-06 23:04:53

@YYAN_ZU

显然的。因为1/n必然是一个0到1之间的小数，用整型存会得到0的结果（因为整型除法是向下取整），最后会发生死循环，永远也到不了k

by chenzait @ 2024-05-07 17:21:11

@YYAN_ZU 浮点数就是小数

by chenzait @ 2024-05-07 17:21:39

@YYAN_ZU 你不用小数怎么做