杨辉三角形–2021蓝桥杯Java组
题目描述
下面的图形是著名的杨辉三角形:
如果我们按从上到下、从左到右的顺序把所有数排成一列,可以得到如下数列:1,1,1,1,2,1,1,3,3,1,1,4,6,4,1,⋯
给定一个正整数 NN,请你输出数列中第一次出现 NN 是在第几个数?
输入描述
输入一个整数 NN。
输出描述
输出一个整数代表答案。
输入输出样例
示例 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到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;
}
}