描述
http://poj.org/problem?id=3685
一个n*n的矩阵,(i,j)的值为i*i+100000*i+j*j-100000*j+i*j,求第m小的值.
Time Limit: 6000MS | Memory Limit: 65536K | |
Total Submissions: 5980 | Accepted: 1700 |
Description
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
Source
分析
与POJ_3579很像.假定一个第m小的值x,如果<=x的值<m,那么x偏小.在统计<=x的值的时候还要用到二分,对于一个确定的j,值是关于i单增的,枚举j,二分查找使得值<=x的最大的i.
注意:
1.第一层二分的边界:最大值是i,j取n,去掉负值;最小值是i,j取n,去掉正值.
2.第二层二分统计个数时,i在(1,n)内不一定存在使得值<=x的,所以二分范围不能是(1.n).如x=-1,n=1,如果在(1,n)内,值只有3,这样最后l=r=1,表示有一个<=x的值,其实一个都没有,所以应该在(0,n)内二分,而这里因为写成了m=l+(r-l+1)/2,有一个"+1",所以(r-l+1)/2>=1,m>=1,所以不必担心会去到0,如果不是这样,在val函数中应加一条:if(i==0) return -100000*n;也就是给0的情况一个最小值,如果有n+1,应赋最大值.也就是假设了左右两个端点,最后如果落在这两个实际不存在的点上,那么就是没有答案.
3.数据范围.整型上限大概2*10^9,这道题极限情况1.75*10^10,必须用long long.检查的时候还是要耐心.
#include<cstdio>
#define ll long long ll q,n,m; ll val(ll i,ll j){ return i*i+*i+j*j-*j+i*j; } ll bsearch(ll j,ll x)
{
ll l=,r=n;
while(l<r)
{
ll m=l+(r-l+)/;
if(val(m,j)<=x) l=m;
else r=m-;
}
return l;
} bool C(ll x)
{
ll cnt=;
for(ll j=;j<=n;j++) cnt+=bsearch(j,x);
return cnt<m;
} void solve()
{
ll l=-*n,r=*n*n+*n;
while(l<r)
{
ll mid=l+(r-l)/;
if(C(mid)) l=mid+;
else r=mid;
}
printf("%lld\n",l);
} void init()
{
scanf("%lld",&q);
while(q--)
{
scanf("%lld%lld",&n,&m);
solve();
}
} int main()
{
freopen("matrix.in","r",stdin);
freopen("matrix.out","w",stdout);
init();
fclose(stdin);
fclose(stdout);
return ;
}