蓝桥训练营-杨辉三角形（java）

思路：
这道题是一道找规律的题目：首先我们需要了解杨辉三角和组合数的关系

即：每一层的数都对应与一个组合数C,下限为行号，上限为列号

通过规律可以得出：每一行每一列上的数字都是单调递增的，而且都是对称的，当我们要寻找第一个出现的数，只需考虑左半部分即可，这样我们就可以再第j列枚举查找第一个大于等于n的数，若其与n相等，则输出其序号；否则，继续在 j − 1列上查找这个数。

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        for(int k = 16; k >= 0; k--){
            int  left = 2 * k;
            int right = Math.max(n, left);
            int r = -1;
            while(left <= right){
                int mid = (left + right) >> 1;
                if(C(mid, k, n) >= n){
                    right = mid - 1;
                    r = mid;
                }else{
                    left = mid + 1;
                }
            }
            if(C(r, k, n) == n){
                System.out.println((long)(r +1) * r/2 + k + 1);
                break;
            }
        }
    }

    static long C(long n , long k, long target){
        long right = 1, left = 1;
        if(k > n / 2){
            k = n - k;
        }
        for (int i = 1; i <= k; i++) {
            right *= n - i + 1;
            left *= i;
            long g = min(right, left);
            right /= g;
            left /= g;
            if(right / left > target){
                return right /left;
            }
        }
        return right / left;
    }
}


    static long min(long a, long b) {
        return b == 0 ? a : min(b, a % b);
    }