杨辉三角形–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

分析：

1. 杨辉三角：第一个数为第零行第零列，则我们观察发现杨辉三角第i行第j列的数字为组合数C(i, j)
2. 杨辉三角每行最大的数为C(i, i / 2), 每列j的最小有效行（之前没出现的数字）是 2 * j行，最大有效行是给定数字的n 的n行（第二列1到n）
3. 注意杨辉三角数字增大按列增大比按行增大快，所以我们按列找。根据数据给定N范围确定最大的列为17，C（33，17） = 1166803110 > 1000000000
4. 本题通过所有样例要写出O(logN)的算法所以不能暴力解决（打表遍历超时,后面大数即使是long也会会溢出）数据范围内一共只遍历17个列，行最大可到1000000000 故我们再遍历列的基础上对行进行二分查找！
5. 本题还是有点东西，考场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;
    }
}