LQ0152 杨辉三角形【模拟】

题目来源：蓝桥杯2021初赛 C++ B组I题

题目描述
下面的图形是著名的杨辉三角形：

如果我们按从上到下、从左到右的顺序把所有数排成一列，可以得到如下数列：
1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, …
给定一个正整数N，请你输出数列中第一次出现N 是在第几个数？

输入描述
输入一个整数 N。

输出描述
输出一个整数代表答案。

输入输出样例
示例 1
输入

6

输出

13

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

问题分析
用模拟法做了一个题解。
对于多输入的测试数据，使用此方法会TLE（超时），可以通过50%的测试样例。

AC的C++语言程序如下：

/* LQ0152 杨辉三角形 */

#include 

using namespace std;

typedef long long LL;
const int LINE = 44721;
LL n, k, line, a[LINE + 1] = {0};

int main()
{
    cin >> n;
    a[0] = k = 1;
    if (n == 1)
        cout << 1 << endl;
    else {
        for (line = 1; line <= LINE; line++) {
            for (int i = line; i >= 1; i--) {
                a[i] += a[i - 1];
                if (a[i] == n) {
                    cout << k + line - i + 1 << endl;
                    return 0;
                }
            }
            k += line + 1;
        }
        cout << n * (n + 1) / 2 + 2;
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

超时的C++程序如下：

/* LQ0152 杨辉三角形 */

#include 
#include 

using namespace std;

typedef long long LL;
const int LINE = 44721;
LL n, k, line, a[LINE + 1];

int main()
{
    int t;
    cin >> t;
    while (t--) {
        memset(a, 0, sizeof a);

        cin >> n;
        a[0] = k = 1;
        if (n == 1)
            cout << 1 << endl;
        else {
            for (line = 1; line <= LINE; line++) {
                for (int i = line; i >= 1; i--) {
                    a[i] += a[i - 1];
                    if (a[i] == n) {
                        cout << k + line - i + 1 << endl;
                        goto end;
                    }
                }
                k += line + 1;
            }
            cout << n * (n + 1) / 2 + 2;
        }
        end:
            ;
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41