本文主要是介绍蓝桥杯 PREV-284 杨辉三角形【第十二届】【省赛】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【分析】
因为这道题的N最大为10亿，如果遍历10亿行肯定会超时，先看一下杨辉三角形的规律。
可以发现每一行都是先递增后递减的，所以当某个值已经大于10亿时就说明不在这一行了。接下来看如何找这个大于10亿的值比较好。首先第一列都是1，第二列（1，2，3...），第三列是的值为（1+2+3...），即（n*n+1）/2，这样解出来n=44721，再算上前面两行，可以定义n为44724行。也就是说，当算到这一行时，第三个数已经超过10亿了，由于此时数列不管向后还是向下都是递增的，所以n只能出现在下一行的第二列，而第二列的值所在位置则正好是前面那些行所有数字的个数+2，即（n*n+1）+2。
另外需要注意变量要定义为long。
import java.util.Scanner;public class Main {public static void main(String[] args) {int i, j;Scanner scanner = new Scanner(System.in);long n = scanner.nextLong();long[] a = new long[44725];a[0] = a[1] = 1L;Long cnt;if(n == 1) {System.out.println(1);return;}else{cnt = 3L;for(i = 3; i < 44725; i++){for(j = i - 1; j >= 1; j --){a[j] += a[j - 1];if(a[j] == n){System.out.println(cnt + i - j);return;}}cnt += i;}}System.out.println((n + 1) * n / 2 + 2);}}
这篇关于蓝桥杯 PREV-284 杨辉三角形【第十二届】【省赛】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
