题目大意：矩阵里面的元素按i*i + 100000 * i + j*j - 100000 * j + i*j填充(i是行，j是列)，求最小的M个数
这一题要用到两次二分，实在是二分法的经典，主要是每一列都是按照行来递增的，每一行我们都用二分法找到比mid小的那些数就好了
参考
1 #include2 #include 3 #include 4 5 using namespace std; 6 typedef long long LL_INT; 7 8 LL_INT getnum(LL_INT, LL_INT); 9 bool judge(LL_INT, LL_INT, const int);10 11 int main(void)//这题双二分法12 {13 int test_sums, size;14 LL_INT M;15 scanf("%d", &test_sums);16 17 while (test_sums--)18 {19 scanf("%d%lld", &size, &M);20 LL_INT lb = -0x3fffffffffffffff, rb = 0x3fffffffffffffff, mid;21 while (rb - lb > 1)22 {23 mid = (lb + rb) / 2;24 if (judge(mid, M, size)) lb = mid;25 else rb = mid;26 }27 printf("%lld\n", rb);28 }29 return 0;30 }31 32 LL_INT getnum(LL_INT i, LL_INT j)33 {34 return i*i + 100000 * i + j*j - 100000 * j + i*j;//注意这题的每一列都是递增的！35 }36 37 bool judge(LL_INT x, LL_INT M, const int N)38 {39 LL_INT line_l, line_r, mid, sum = 0;40 for (int col = 1; col <= N; col++)41 {42 line_l = 1; line_r = N + 1;43 if (getnum(N, col) <= x)//先判断一下这个，还可以剪枝，而且还能避免判断n=1的时候的错误44 sum += N;45 else46 {47 while (line_r - line_l > 1)48 {49 mid = (line_l + line_r) / 2;50 if (getnum(mid, col) <= x) line_l = mid;51 else line_r = mid;52 }53 if (getnum(line_l, col) <= x)54 sum += line_l;55 else56 sum += line_l - 1;57 }58 }59 return sum < M;60 }
