杨辉三角形--2021蓝桥杯Java组

杨辉三角形–2021蓝桥杯Java组

题目描述

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

杨辉三角形--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;
    }
}
上一篇:mark down 学习


下一篇:106 动态中位数(对顶堆)