POJ - 3685 Matrix 二分套二分

传送门：POJ3685

题意：给定一个矩阵的通项公式，问第m大的数是多少。

思路：根据 i² + 100000 × i + j² - 100000 × j + i × j  我们可以发现，对于固定的j，式子整体值的变化是随i的变化单调的。因此我们可以先二分答案，然后检查是否满足的时候对每一列再用一个二分，这样时间就够使了。

因为会出现大小相同的元素，因此二分的时候一定要注意条件的判断，很容易出错。

代码：

#include<iostream>
#include<stdio.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
#define pi acos(-1)
#define inf 0x3f3f3f3f3f3f3f3f
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define rep(i,x,n) for(int i=x;i<n;i++)
#define per(i,n,x) for(int i=n;i>=x;i--)
using namespace std;
typedef pair<int,int>P;
const int MAXN=100010;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
ll n, m;
ll f(int i, int j)
{
	return 1ll * i * i + 100000ll * i + 1ll * j * j - 100000ll * j + 1ll * i * j;
}
bool check(ll k)
{
	int l = 1, r = n, mid;
	ll sum = 0;
	for(int i = 1; i <= n; i++)
	{
		l = 1;
		r = n;
		while(l <= r)
		{
			mid = (l + r) >> 1;
			if(f(mid, i) <= k)
			l = mid + 1;
			else
			r = mid - 1;
		}
		sum += l - 1;
	}
	return sum < m;
}
int main()
{
	int T;
	cin >> T;
	while(T--)
	{
		scanf("%lld %lld", &n, &m);
		ll l = -inf, r = inf, mid;
		while(l <= r)
		{
			mid = (l + r) >> 1;
			if(check(mid))
			l = mid + 1;
			else
			r = mid - 1;
		}
		printf("%lld\n", l);
	}
 	return 0;
}