POJ-3685---Matrix (二分）

Matrix

Time Limit: 6000MS		Memory Limit: 65536K
Total Submissions: 7248		Accepted: 2144

Description

Given a N × N matrix A, whose element in the i-th row andj-th column A_ij is an number that equals i² + 100000 ×i + j² - 100000 × j + i × j, you are to find theM-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 Founder Monthly Contest – 2008.08.31, windy7926778

题意：有一个N*N的矩阵，矩阵中每个点的值由题中给的公式计算出，问矩阵中第m小的数是什么；

思路：首先可以打个表会发现矩阵的每一列是随i增大单调递增的，那么现在就可以用二分来求答案，对于每次二分得到的mid ，再去矩阵中二分每一列求得小于mid的数的个数，最后求得答案；注意这题要用long long，开始wa了一发，然后全部改成long long过了；（附上一张打的表）

AC代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
LL n,m;
LL calculate(LL i,LL j)//计算矩阵中的值
{
    return i*i+100000*i+j*j-100000*j+i*j;
}
LL Count(LL val)//统计比val小的数的个数
{
    LL cnt=0;
    for(LL i=1;i<=n;i++)//枚举每一列
    {
        LL l=0,r=n+1;
        while(r-l>1)
        {
            LL mid=(l+r)>>1;
            if(calculate(mid,i)>=val) r=mid;
            else l=mid;
        }
        cnt+=l;
    }
    return cnt;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld%lld",&n,&m);
        LL l=-100000*n,r=n*n+100000*n+n*n*2;//最初r和l取极大极小值
        while(r-l>1)
        {
            LL mid=(l+r)>>1;
            if(Count(mid)>=m) r=mid;//
            else l=mid;
        }
        printf("%lld\n",l);
    }
    return 0;
}