求助，为什么会TLE？

Kirisamex @ 2022-08-06 09:52:50

#include <iostream>
using namespace std;

double s(int n)
{
    double sum = 0;
    for(int i = 1; i <= n; i++)
    {
        sum += 1 / (i * 1.0);
    }
    return sum;
}

int main()
{
    int k;
    cin >> k;
    int n = 0;
    while(true)
    {
        n++;
        if(s(n) > k)
        {
            cout << n << endl;
            break;
        }
    }
    return 0;
}

by rsrsr @ 2022-08-06 09:55:37

有没有一种可能，你可以用Sn-1推Sn，而不用每次都算一遍

by zxy_sh @ 2022-08-06 09:56:30

时间复杂度太高了 你得优化一下算法

by CurryCute @ 2022-08-06 09:57:30

你的while无意义，无形中多了一层循环，所以这样写就行

#include <iostream>
using namespace std;
double n,a,i = 0;
int main(){
    cin >> n;
    while(n >= a){
        i++;
        a += 1/i;
    }
    cout << i;
}

by Kirisamex @ 2022-08-06 10:02:03

@ruawry 对哦，可以用s(n - 1)来推s(n)

by I_wil_ak_IOI @ 2022-08-06 10:23:23

时间复杂度不合法

by Accepted_please @ 2022-08-06 11:14:27

#include<iostream>
using namespace std;
int main()
{
    long long k,n=0;
    double sum=0;
    cin>>k;
    for(int i=1;;i++)
    {
        sum+=1.0/i;
        n++;
        if(sum>k)
          break;
    }
    cout<<n<<endl;
    return 0;
}

by Polarie @ 2022-08-12 19:18:07

#include<stdio.h>
int
main(){
    int k,n;
    double sum=0.0;
    scanf("%d",&k);
    for(n=1;;n++){
     sum+=1.0/n;
     if(sum>k*1.0)
      break;
    }
    printf("%d",n);
    return 0;
}

by Polarie @ 2022-08-12 19:18:52

试试这样?