欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Matrix POJ - 3685(二分套二分)

程序员文章站 2022-03-13 22:45:56
...

Given a N × N matrix A, whose element in the i-th row and j-th column Aij is an number that equals i2 + 100000 × i + j2 - 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
12

1 1

2 1

2 2

2 3

2 4

3 1

3 2

3 8

3 9

5 1

5 25

5 10
Sample Output
3
-99993
3
12
100007
-199987
-99993
100019
200013
-399969
400031
-99939
其实我感觉这个题不用二分也可以做的。。
因为矩阵中的值是有规律的。但是那样做情况特别多,但是二分的话就不用考虑那么多的情况。
首先我们先去二分答案,按着这个答案去判断在原数组中有多少个数字小于这个值。对于矩阵中的那些数,每一列都是呈现递增状态,所以我们可以二分出每一列小于等于这个值的个数,想加起来就是这个矩阵中小于这个值的个数,于m作比较,然后不断的去更新答案。
代码如下:

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;

ll n,m;

inline ll fun(ll i,ll j)
{
	return (i*i+j*j+i*j+100000*(i-j)); 
}
inline ll solve(int pos,ll x)
{
	int l=1,r=n,mid,ans=0;
	while(l<=r)
	{
		mid=l+r>>1;
		if(fun(mid*1ll,pos*1ll)<=x)
		{
			ans=mid;
			l=mid+1;
		}
		else r=mid-1;
	}
	return ans;
}
inline bool judge(ll x)
{
	ll sum=0;
	for(int i=1;i<=n;i++)
		sum+=solve(i,x);
	return sum<m;
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%lld%lld",&n,&m);
		ll l=-1e10,r=1e10,mid;
		ll ans=l;
		while(l<=r)
		{
			mid=l+r>>1;
			if(judge(mid))
			{
				ans=mid;
				l=mid+1;
			}
			else r=mid-1;
		}
		printf("%lld\n",ans+1);
	}
	return 0;
}

努力加油a啊,(o)/~

相关标签: 二分套二分