我要评论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：，
- Space：，
方法二：
复杂度分析
- Time：，
- Space：，
本文地址：https://blog.csdn.net/qq_43539599/article/details/108118753
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请点击进行留言回复，万千网友为您解惑！
网友评论