[数据结构与算法]蓝桥真题：杨辉三角形（思维+二分）

正文

题目描述

题目思路及代码

杨辉三角的基本性质：左右对称，所以只要在杨辉三角右半边出现过的数都会在左半边出现过，且位置是对称的，所以答案一定是在左半边

思路：对于每一斜行和竖行从上至下是依次增大的，需要明确的一点是所有的数都会在杨辉三角中出现，比如x，一定会有C(x,1)对应于x，所以不用担心有无解的情况，但是我们需要找到数值为x的最靠上的位置就需要从下往上枚举，因为如果x第一次出现在(i,j)这个位置，那么这个位置左上和上方以及右上的数都会比x要小，所以我们可以枚举斜行，利用二分来枚举在每一斜行中出现的位置即可，注意是从下往上枚举。通过上述性质2可以得出通过组合数优化的杨辉三角计算方法。
代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll maxn=1e5+10;
ll n;
ll C(ll x,ll y){//计算组合数
    ll ans=1;
    for(int i=x,j=1;j<=y;j++,i--){
        ans=ans*i/j;
        if(ans>n)return ans;
    }
    return ans;
}
ll cha(ll k){
    ll l=2*k,r=max(n,l);
    //二分找出结果
    while(l<r){
        ll mid=(l+r)>>1;
        if(C(mid,k)>=n){
            r=mid;
        }else{
            l=mid+1;
        }
    }
    if(C(l,k)!=n)return 0;
    ll ans=l*(l+1)/2+k+1;//用等差数列进行求在这行之前所有数字
    cout<<ans;
    return 1;
}
int main(){
    cin>>n;
    ll ans=n;
    for(int i=16;;i--){
        if(cha(i))break;
    }

	return 0;
}

结语