杨辉三角形–2021蓝桥杯Java组
题目描述
下面的图形是著名的杨辉三角形：
如果我们按从上到下、从左到右的顺序把所有数排成一列，可以得到如下数列：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； 对于所有评测用例,10000000001≤N≤1000000000。
运行限制
最大运行时间：1s
最大运行内存: 256M
分析：
- 杨辉三角：第一个数为第零行第零列，则我们观察发现杨辉三角第i行第j列的数字为组合数C(i, j)
- 杨辉三角每行最大的数为C(i, i / 2), 每列j的最小有效行（之前没出现的数字）是 2 * j行，最大有效行是给定数字的n 的n行（第1(j)列1到n）
- 注意杨辉三角数字增大按列增大比按行增大快，所以我们按列找。根据数据给定N范围确定最大的列为17，C（33，17） = 1166803110 > 1000000000
- 本题通过所有样例要写出O(logN)的算法所以不能暴力解决（打表遍历超时,后面大数即使是long也会溢出）数据范围内一共只遍历17个列，行最大可到1000000000 故我们再遍历列的基础上对行进行二分查找！
- 本题还是有点东西，考场AC有点难度
AC代码：
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt();for(int k = 17; k >= 0; k--){int head = 2 * k; //每列最小有效行int tail = Math.max(n, head); // 每列最大有效行int r = -1;while(head <= tail){int mid = (head + tail) >> 1;if(combination(mid, k, n) >= n){tail = mid - 1;r = mid;}else{head = mid + 1;}}if(combination(r, k, n) == n){System.out.println((long)(r +1 ) * r/2 + k + 1);break;}}scan.close();}static long gcd(long a, long b) {return b == 0 ? a : gcd(b, a % b);}//算第i行第j列的组合数 与 给定数target的大小//运算组合过程中判断，如果比target大，直接返回当前数字//这里在小于等于target的时候才会将C（i，j）组合数算完并返回static long combination(long n , long k, long target){long up = 1, down = 1;if(k > n / 2){k = n - k;}for (int i = 1; i <= k; i++) {up *= n - i + 1;down *= i;long g = gcd(up, down);up /= g;down /= g;if(up / down > target){return up /down;}}return up / down;}
}
