43 lines
1.6 KiB
C++
43 lines
1.6 KiB
C++
// lanqiao 1457 杨辉三角形(优化解法)
|
||
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
#define int long long
|
||
const int N = 1e5 + 10;
|
||
int a[N], b[N];
|
||
signed main(){
|
||
int n; cin >> n;
|
||
a[0] = b[0] = 1;
|
||
if (n == 1){
|
||
cout << 1 << endl;
|
||
return 0;
|
||
}
|
||
/*
|
||
如果某一行第二个数是n，那么第三个数一定是n(n-1)/2,算到44723行
|
||
44723*44723>10亿，所以算到前44723行即可
|
||
*/
|
||
for (int i = 3; i <= 44723; i++){
|
||
// 对于本题的规模，使用杨辉三角模版求解会超时，由于杨辉三角是对称的
|
||
// 所以我们只需要求解一半即可
|
||
for(int j = 1; j <= i/2; j++){
|
||
if (j == i/2 && i%2 == 1) b[j] = 2 * a[j - 1];
|
||
else b[j] = a[j - 1] + a[j];
|
||
a[j - 1] = b[j - 1]; // 更新滚动数组
|
||
if (b[j] == n){
|
||
// 如果找到了n, 则前i-1行, 按照等差数列计算一共有i*(i-1)/2个元素
|
||
// 由于当前行我们是从第二个元素开始算的，所以需要+j+i
|
||
cout << i * (i - 1)/2 + j + 1 << endl;
|
||
return 0;
|
||
}
|
||
}
|
||
a[i/2] = b[i/2];
|
||
}
|
||
// 对于超过44723行的情况，其实只需要考虑每一行的第二个元素即可，第三个元素一定越界
|
||
// 而每一行的第二个数字正好就是行号-1，假设某一行第二个数字是n，则行号i=n+1
|
||
// 所以到当前元素的总个数为n*（n+1）/2
|
||
// 总的来说，这个表达式计算超过44723行时，第一次出现n的位置
|
||
cout << n*(n+1)/2 + 2 << endl;
|
||
return 0;
|
||
}
|
||
/* test samples -> 13
|
||
6
|
||
*/ |