题目链接:杨辉三角形 - 蓝桥云课 (lanqiao.cn)

题目描述

下面的图形是著名的杨辉三角形：

如果我们按从上到下、从左到右的顺序把所有数排成一列，可以得到如下数列： 1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, \cdots1,1,1,1,2,1,1,3,3,1,1,4,6,4,1,⋯

给定一个正整数 NN，请你输出数列中第一次出现 NN 是在第几个数？

输入描述

输入一个整数 NN。

输出描述

输出一个整数代表答案。

输入输出样例

示例 1

输入

6

输出

13

评测用例规模与约定

对于 20%​​ 的评测用例，1≤N≤10​； 对于所有评测用例，1≤N≤1000000000。

数挺大的，整整十个亿，先给你们来个暴力的(非AC代码)：

简单思路就是得出每一行的元素个数，然后看是否是目的数。很简单，但是时长和内存都受不了，自己慢慢来优化。

#include <iostream>
using namespace std;
long long a[100010],b[100010];
int main()
{a[0]=1,a[1]=1;b[0]=1,b[1]=1;long long n;cin>>n;if(n==1){cout<<1;return 0;}for(int i=3;i<=100000;i++){for(int j=1;j<=i-2;j++){b[j]=a[j-1]+a[j];if(b[j]==n){cout<<i*(i-1)/2+j+1;return 0;}}b[i-1]=1;for(int j=0;j<i;j++){a[j]=b[j];}}cout<<n/2*(n+1)+2;// 请在此输入您的代码return 0;
}

1.我们发现，杨辉三角是对称的，那么我们只要维护一半的数即可。

2.我们还可以事先找出第一次最小数大于1e9的那一行。

3.然后时刻维护两个数组。

4.快速判断，如果未找到目的数并且某一行最小的数大于n，那么我们直接可以判断在这个数第一次出现在第n行，并且是第二个数。

AC代码:

#include <iostream>
using namespace std;
long long a[100010],b[100010];//开两个数组，一个保存上一行那一半的数，一个保存目的行那一半的数
int main()
{a[0]=1;b[0]=1;long long n;cin>>n;if(n==1){cout<<1;return 0;}for(int i=3;i<=44723;i++){//这个是最高循环次数，你可以自己找int m=i/2;//只要一半for(int j=1;j<=m;j++){if(j==m&&i%2==1){//如果行数为奇数那么就有个中间数，就是上一行前面数的两倍，因为我们只算一半。b[j]=a[j-1]*2;}else{b[j]=a[j-1]+a[j];//杨辉三角}a[j-1]=b[j-1];//更新a数组if(b[j]==n){cout<<i*(i-1)/2+j+1;//输出return 0;}}a[m]=b[m];//更新a数组if(b[1]>n){//快速判断，我们想想，在没找到目的数之前，如果有一行的第二个数比目的数还要大，那么肯定就不会再次出现，直接快速判断输出结果为n行的第二个数。cout<<n*(n+1)/2+2;return 0;}}cout<<n*(n+1)/2+2;//防止溢出return 0;
}