2021年蓝桥杯——杨辉三角形

题目描述：

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

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

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

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

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

输入输出样例
示例 1
输入

6
1
输出

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

运行限制
最大运行时间：1s
最大运行内存: 256M

解题思路：

        提到杨辉三角并不陌生，本题最先想到的还是暴力破解，暴力算出每一行的数字直到遇到目标数，返回结果。但想要拿到全部样例分，在10的9次方这个大数据下这方法显然行不通。

        首先最先想到的应该是杨辉三角的左右两边数据对称，结合杨辉三角的数据生成特点和下图：

所以在遍历的时候，可以只遍历左边的图，且最大值第一次出现一定是在图的左边。且每个斜行的组合底数相同，每一斜行是单调递增的且中数最小。

最大测试用例为10的9次方，根据组合计算只需从第16斜行枚举到，并且每一斜行采用二分查找。

代码块分析：

主函数

static int n;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        for(int i = 16;;i--){
            if(check(i)){
                break;
            }
        }
        scan.close();
    }

i代表从第16斜行开始遍历，并且调用check函数，即从C（n,16）开始遍历。

check函数

static boolean check(int i)
    {
        int r = 2 * i, l = Math.max(n,r);
        while(r < l)
        {
            int mid = (l - r) / 2 + r;
            if(C(mid, i) >= n) l = mid;
            else r = mid + 1;
        }
        if(C(r, i) != n)
            return false;
        else{
            System.out.println(((long) (r + 1) * r / 2) + i + 1);
            return true;
        }
    }

C函数：计算组合数值

static long C(int a, int b){
        long ans = 1;
        for(int i = a, j = 1; j <= b; j++, i--){
            ans = ans * i / j;
            if(ans > n){
                // 避免ans超过long的最大值
                return ans;
            }
        }
        return ans;
    }

总代码

package lanqiao12;
import java.util.Scanner;
public class main {
    static int n;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        for(int i = 16;;i--){
            if(check(i)){
                break;
            }
        }
        scan.close();
    }
    static boolean check(int i)
    {
        int r = 2 * i, l = Math.max(n,r);
        while(r < l)
        {
            int mid = (l - r) / 2 + r;
            if(C(mid, i) >= n) l = mid;
            else r = mid + 1;
        }
        if(C(r, i) != n)
            return false;
        else{
            System.out.println(((long) (r + 1) * r / 2) + i + 1);
            return true;
        }
    }
    static long C(int a, int b){
        long ans = 1;
        for(int i = a, j = 1; j <= b; j++, i--){
            ans = ans * i / j;
            if(ans > n){
                // 避免ans超过long的最大值
                return ans;
            }
        }
        return ans;
    }
}