题解 | #求正数数组的最小不可组成和#

#include <iostream>
#include <cstdio>
using namespace std;

int main() {
    int board = -1;
    long long ans[100000];
    ans[0] = 1;
    ans[1] = 2;
    for (int i = 2; i < 100000; i++) {
        long long next = ans[i - 1] + ans[i - 2];
        if( board == -1 && next >= 1000000 ) //首次出现
        {
            board  = i+1;
        }
        ans[i] = next % 1000000;
    }
    
    int n;
    while (cin >> n) {
        long long f = ans[n - 1];
        if(n>=board)
            printf("%06d\n",f);
        else
        printf("%d\n", f);
        }
    
}

• 思路：

1. 利用一个数组来保存从1~100000的数
2. 用的时候再去取就好了
3. 时间复杂度低，空间复杂度高。属于用空间来换时间

• 注意事项：

1. 注意首次出现大于1000000的数，后面的数就要输出后6位了，假如不做处理，后面的数有可能低于6位。if( board == -1 && next >= 1000000 ) //首次出现