第十二届蓝桥杯B组C/C++省赛—H题（杨辉三角）

【摘要】题目：ACWing—3421

分析
1、首先通过画图，发现杨辉三角对称，而题目要求找到数 n 最早出现的位置，那么我们可以确定，n最早出现的位置一定在左半边，而且最中间的是该行最大的数 2、通过图，我们可以发现通过行和列的枚举是不好的，看数据1e9也就是十亿，这是个很大的工程，因此我们试想可不可以从斜行来观察呢？？
下图我们可以观察到，第1斜行的1=C（0…

题目：ACWing—3421

在这里插入图片描述

分析

1、首先通过画图，发现杨辉三角对称，而题目要求找到数 n 最早出现的位置，那么我们可以确定，n最早出现的位置一定在左半边，而且最中间的是该行最大的数
在这里插入图片描述
2、通过图，我们可以发现通过行和列的枚举是不好的，看数据1e9也就是十亿，这是个很大的工程，因此我们试想可不可以从斜行来观察呢？？

下图我们可以观察到，第1斜行的1=C（0,0），第二斜行的2=C（2,1），第三斜行的6=C（4,2）,第四斜行的20=C（6,3）…
也就是说，如果我设共 i 斜行，那么第 i 斜行的第一个数为C（2*i，i），同时它是该斜行中最小的数字
那么我们一定可以找到1e9的位置

在这里插入图片描述
3、1e9的位置确定

C（2*i，i）的计算（当然是指计算机手算的时候，代码里原始运算就好）
显然C（32,16）< 1e9，而C（34,17）> 1e9，因此我们可以对前16行进行枚举

4、枚举顺序

首先对于左半边杨辉三角来说，每行最大的数一定出现在该行末尾，同时它也是该数最早出现的位置
因此我们不妨从第16斜行开始枚举，只要出现等于 n 的数直接返回位置即可
对于查找，我们可以对每个斜行采用二分的方法查找n
对于位置，我们可以在查找的时候确定，n所在行 r（不是斜行）和所在斜行 k ，然后通过等差公式 r*（r+1）/2 计算它之前数目的个数再加上 k+1

例如：n = 20 （由于推到，第一行行号为 0 ，斜行行号也是 0）

查找过程我们可以确定20在第7行，实际返回 r = 6 ，在第 4 斜行，但此时 k 是 3，因此 k+1
结果 ans = 6*7/2 + 3 + 1 = 25

在这里插入图片描述
5、时间复杂度分析

枚举16斜行 –> O（16）
二分查找 –> O（logn）
综合起来，算法时间复杂度为 O（16logn）

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
int n;
LL C(int a, int b)   //计算C（a，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)
{ // 二分该斜行,找到大于等于该值的第一个数 // 左边界2k，右边界为max(l, n)取二者最大，避免右边界小于左边界 int l = 2 * k, r = max(n,l); while(l < r) { int mid = l + r >> 1; if(C(mid, k) >= n) r = mid; else l = mid + 1; } if(C(r, k) != n) return false; cout << 1ll*(r + 1) * r / 2 + k + 1 << endl; return true;
}
int main()
{ cin >> n; // 从第16斜行枚举 for(int i = 16; ; i--) if(check(i)) break; return 0;
}

  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42