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

POJ-3685---Matrix (二分)

程序员文章站 2024-03-17 15:08:34
...
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 Aij is an number that equals i2 + 100000 ×i + j2 - 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 ≤ MN × 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过了;(附上一张打的表)

POJ-3685---Matrix (二分)

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;
}