POJ 3685：Matrix 二分

Matrix

Time Limit: 6000MS		Memory Limit: 65536K
Total Submissions: 5489		Accepted: 1511

Description

Given a N × N matrix A, whose element in the i-th row and j-th column A_ij is an number that equals i² + 100000 × i + j² - 100000 × j + i × j, you are to find the M-th smallest element in the matrix.

Input

The first line of input is the number of test case.
For each test case there is only one line contains two integers, N(1 ≤ N ≤ 50,000) and M(1 ≤ M ≤ N × N). There is a blank line before each test case.

Output

For each test case output the answer on a single line.

Sample Input

Sample Output

给了一个N*N的矩阵，每个位置上的数由该位置的下标i,j决定。然后问这个矩阵中第m小的数。

通过这道题好好总结了一下二分，总算是深刻理解了一下。

第一个二分枚举答案，第二个二分，通过公式可知，函数跟j不是单调的关系，但跟i是单调的关系，所以每次枚举j，然后二分i的值。

代码：

#include <iostream>  
#include <algorithm>  
#include <cmath>  
#include <vector>  
#include <string>  
#include <cstring>  
#pragma warning(disable:4996)  
using namespace std;

#define maxn 1e12
typedef long long ll;

ll m, n;
ll le, ri, mid;

ll cal(ll i, ll j)
{
	return i*i + 100000 * i + j*j - 100000 * j + i*j;
}

ll check(ll x)
{
	ll i, le, ri, mid, cnt;
	
	ll temp;
	cnt = 0;
	for (i = 1; i <= n; i++)
	{
		le = 1;//mid不能取到0，所以这里的le取1
		ri = n + 1;//因为mid可能要取到n，所以这里的ri要取到比n大的数
		
		mid = le + (ri - le) / 2;
		while (le < ri)
		{
			temp = cal(mid, i);
			if (cal(mid, i) < x)
			{
				le = mid + 1;
			}
			else
			{
				ri = mid ;
			}
			mid = le + (ri - le) / 2;
		}
		cnt += (mid - 1);//经过计算，这里始终是多计算了一个1，所以要在这里把它扣掉
	}
	return cnt;
}

int main()
{
	//freopen("i.txt", "r", stdin);
	//freopen("o.txt", "w", stdout);

	int test;
	scanf("%d", &test);

	while (test--)
	{
		scanf("%lld%lld", &n, &m);
		le = -maxn;
		ri = maxn;

		mid = le + (ri - le) / 2;
		while (le < ri)
		{
			if (check(mid) < m)//检查小于 mid 的个数
			{
				le = mid + 1;
			}
			else
			{
				ri = mid;
			}
			mid = le + (ri - le) / 2;
		}
		printf("%lld
", mid-1);//有m个小于mid的数，所以第m大的数就是mid-1
	}

	//system("pause");
	return 0;
}