蓝桥杯2021年第十二届省赛真题-杨辉三角形(JAVA题解)

解题思路:

思维+二分搜索
注意事项:

必须用二分搜索，否则只能得90分。。。

参考代码:

import java.util.*;
import java.io.*;

// https://www.dotcpp.com/oj/problem2610.html
public class Main {
	static StreamTokenizer cin;
	static PrintWriter out;
	static int N;
	public static void main(String[] args) throws IOException{
		cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		out = new PrintWriter(new OutputStreamWriter(System.out));
		N = nextInt();
		if(N==1) 
			out.println(1);
		else {
			for(int i = 17; i > 0; i--) {
				int k = (i*2+1)>>1;
				boolean flag = false;
				long left = i<<1;
				long right = N;
				while(left <= right) {
					long j = (left+right)>>1;  // 计算第j行
					long m = C((int)j, k);
					if(m == N) {
						long dis = (long)(1+j)*j/2+k+1;
						out.println(dis);
						flag = true;
						break;
					}else if(m > N)
						right = j-1;
					else {
						left = j+1;
					}
				}
				if(flag)
					break;
				
			}
		}

	out.flush();
	out.close();
	}
	
	static int nextInt() throws IOException{
		cin.nextToken();
		return (int)cin.nval;
	}
	
	static long C(int a, int b) {  // 行列
		long mul = 1;
		long c = b;
		for(int i = a, j=1;j <= b; i--, j++) {
			mul *= i;
			mul /= j;
			if(mul > N)
				return mul;
		}
		return mul;

	}

}