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;}
}