[蓝桥杯 2021 省 B] 杨辉三角形 详细过程+注释_p8749 [蓝桥杯 2021 省 b] 杨辉三角形

原题链接:P8749 [蓝桥杯 2021 省 B] 杨辉三角形

题目描述

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

如果我们按从上到下、从左到右的顺序把所有数排成一列，可以得到如下数列：

1,1,1,1,2,1,1,3,3,1,1,4,6,4,1,…

给定一个正整数 N，请你输出数列中第一次出现 N 是在第几个数。

输入格式

输入一个整数 N 。

输出格式

输出一个整数代表答案。

输入输出样例

输入 6

输出 13

说明/提示

对于 20% 的评测用例, 1≤N≤10;

对于所有评测用例, 1≤N≤1e9 。

蓝桥杯 2021 第一轮省赛 B 组 H 题。

---

解题思路：

首先由于杨辉三角形是对称的，所以只需要在三角形的左半边查找，再根据杨辉三角形的性质，第i行第j列的值为C(i,j)，可以得到下面部分(红色为有效的查找区间)

首先由于数据范围是10的9次方，所以暴力肯定不行

由于每一列的元素具有单调性，考虑使用二分

思考一下应该从哪一列开始查找，显然如果两个元素是相同的，那么显然行数更小的那个数最先出现

如图，C(4,2)显然比C(6,1)先出现

查找顺序:如果每一列都进行二分查找,那么从哪一列开始找才能最先找到最优解呢？

假设我在C(x,4)的第8行第4列C(8,4)找到了70这个数，那么我再到前面找，假设我在第2列又找到了70，也就是C(x,2)=70,那么这个x一定会大于8,那么C(x,2)的这个元素出现的顺序一定在C(8,4)之后(因为行数小的最先出现)

所以我们按列数从大到小，依次二分查找每一列元素，直到第一次找到这个元素为止

由图中可知，每一列第一个元素是C(i,i/2)，那么根据数据范围，通过敲计算器或者敲一个C(i,i/2)可知:C(34,17)=2333606220，超过了1e9，所以只需要C(32,16)开始往下枚举每一列即可

代码实现