【蓝桥杯C++ B组】杨辉三角形_蓝桥杯b 杨辉三角

二分

1、思路怎么想？

（1）因为杨辉三角是左右对称的，所以n最早出现的位置只能是左半部分。

所以，只看左半部分，

（2）每一行中越靠近中间的数越大，每一斜行中越往下越大。 所以从最下面的斜行往上枚举。

 （3） n最大1e9，C(34, 17) > 1e9, C(32, 16) < 1e9，因此只要枚举前16个斜行即可！

（4） 可以发现性质：

1）每一斜行从上到下递增

2）每一横行从中间到两边依次递

因此我们直接从中间对称轴倒序二分找起即可，

（5）二分查找每一斜行，

1）因为，每个斜行的第一个数是C(2k, k)依次为C(2k + 1, k)...，并且还是递增的。

只有上标变，所以我们只枚举上标，从2k到max(n , l)。

2）为什么是到max(n , l)？

是因为，从中间沿斜行往下递增，所以，如果n这个数在该斜行内，那么必然n > l

3）因此，

二分的左右端点：l：2k，r：max(n, l)

右端点一定不能比左端点小！

特例：否则当n=1时，会出问题！

（6）因为二分查找的是上标，所以我们还需写一个函数，去求组合数

用于与数字n比较，查找

（7）最后查找到之后，求该数的位置

C(r, k)对应的顺序值为：(r + 1) * r / 2 + k + 1

2、代码怎么写？

#include <iostream>
#include <algorithm>
#include <cstring>
 
using namespace std;
 
typedef long long LL;
int n;
 
//3、求组合数
// C(a, b) = a!/b!(a-b)! = a * (a-1) .. b个 / b!
LL c(int a , int b)
{
    LL res = 1;
    for( int i = a , j = 1 ; j <= b ; i -- , j ++ )
    {
        res = res * i / j;
        if(res > n) return res;// 大于n没有意义并且防止爆LL
    }
    return res;
}
 
 
bool check( int k )
{
    //2、二分查找
    // 二分该斜行,找到大于等于该值的第一个数
    // 左边界2k，右边界为max(l, n)取二者最大即可！
    LL l = 2 * k , r = max(l , (LL)n);
    while(l < r)
    {
        LL mid = l + r >> 1;
        if(c(mid , k) >= n) r = mid;//c(mid , k)表示组合数
        else l = mid + 1;
    }
    
    if(c(r , k) != n) return false;//不在该斜行中
    cout << (r + 1) * r / 2 + k + 1 << endl;
    //C(r, k)对应的顺序值为：(r + 1) * r / 2 + k + 1
    return true;
}
 
int main()
{
    cin >> n;
    //1、枚举每一斜行，从第16个斜行开始枚举
    for( int k = 16 ; ; k -- )
        if(check(k))
            break;
    
    return 0;
}

一股温暖的激流刹那间漫过了他的心间。那灯光下，有他亲爱的家——亲人们的脸庞都在他的眼前浮现出来了。

                                             ——《平凡的世界》第二十三章