【递推】B004_LQ_自描述序列（优化）

https://blog.csdn.net/weixin_42318538/article/details/89316331
小明在研究一个序列，叫Golomb自描述序列，不妨将其记作{G(n)}。这个序列有2个很有趣的性质:

对于任意正整数n，n在整个序列中恰好出现G(n)次。这个序列是不下降的。以下是{G(n)}的前几项：

n 1 2 3 4 5 6 7 8 9 10 11 12 13
G(n) 1 2 2 3 3 4 4 4 5 5 5 6 6

给定一个整数n，你能帮小明算出G(n)的值吗？

输入
一个整数n

输出
一个整数G(n)

样例输入
13
样例输出
6

对于30%的数据，1 <= n <= 1000000
对于70%的数据，1 <= n <= 1000000000
对于100%的数据，1 <= n <= 2000000000000000

方法一：暴力

#include<bits/stdc++.h>
using namespace std;
// n    1 2 3 4 5 6 7 8 9 10 11 12 13
// G(n) 1 2 2 3 3 4 4 4 5 5 5 6 6
const int N=1e6+5;
typedef long long ll;

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n; ll g[N]; cin>>n;  
    g[1]=1, g[2]=2;
    for (ll i=2, j=2; i<N; i++)
    for (int c=0; c<g[i]&&j<N; c++) {
        g[j++]=i;
    }
    cout << g[n];
    return 0;
}

感觉还可以优化下…

复杂度分析

• Time：$O()$，
• Space：$O()$，

---

方法二：

复杂度分析

• Time：$O()$，
• Space：$O()$，

本文地址：https://blog.csdn.net/qq_43539599/article/details/108118753