今夜我做起了上届蓝桥杯的一道大题，让我深有感触，在蓝桥官网上总算磕磕绊绊地把这道题做到了满分，其中有参考其他博客的思路，毕竟难做的题才更有助于自己提升，所以现在就写了一篇博客来记录一下这道题。
//这是道找规律的题，
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
//如图，我多列举了几行，题目中要求找n最先出现的位置，首先因为对称可以把右边三角忽略，
//以1，2，6，20划一条对称轴，最先想到的就是暴力把左边挨行遍历完就可以找到答案，但是不适合大数，
//并且计算时需要借助C函数的上下标来获取每个位置的数值，所以要换一种方法，能够找到n最先出现的位置，又能够适合大数，计算方便
//这时候我们已经发现任取一个数n，最靠近对称轴的n的位置就是最先出现的位置，横看成岭侧成峰，我们可以从最靠近对称轴的斜线找，沿斜线发向，
//沿斜线方向数值依次增加，一条斜线上不存在相同的数，所以这个方法是比较可行的，假如n特别大时，我们就需要在斜线上遍历n级别个数，这无疑会超时，
//根据斜线上数值递增的特点，找该条斜线上是否存在n就方便了许多，可以采取二分的方法，时间复杂度便降到了log以2为底n的对数，
//就不用怕超时
//
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n=0;
ll low=0;
ll C(ll loww,ll highh){
ll res=1;
for(ll i=1;i<=highh;i++){
res*=loww;
res/=i;
loww--;
if(res>n) return res;//易漏点，如果已经明确res大于n了，就可以返回了，万一数据过大导致数据出错，出现负数的情况，就不能得到正确的结果
}
return res;
}
bool find(ll line){
// for(ll i=2*line;i<=n;i++){
// if(C(i,line)==n){
// low=i;
// return true;
// }
// }
// return false;
// 上面注释部分会超时
ll l=2*line,r=n;
while(l<r){
ll mid=(l+r)/2;
if(C(mid,line)==n){
low=mid;
return true;
}
else if(C(mid,line)>n){
r=mid-1;
}
else{
l=mid+1;
}
}
if(C(l,line)==n){
low=l;
return true;
}
return false;
}
int main(){
cin>>n;
if(n==1){
cout<<1;
return 0;
}
for(ll k=17;k>=1;k--){
if(find(k)){
cout<<low*(low+1)/2+k+1;
break;
}
}
}
新手小白，欢迎来踢