首页 > 学院 > 开发设计 > 正文

POJ 3685 Matrix 详细题解 (二分嵌套)

2019-11-06 06:49:26
字体:
来源:转载
供稿:网友

Matrix
Time Limit: 6000MS Memory Limit: 65536K
Total Submissions: 5489 Accepted: 1511

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

121 12 12 22 32 43 13 23 83 95 15 255 10

Sample Output

3-99993312100007-199987-99993100019200013-399969400031-99939

题意:给了一个N*N的矩阵,每个位置上的数由该位置的下标i,j决定。然后问这个矩阵中第m小的数。

思路:第一个二分枚举答案,然后就要判断这个数前面有几个数,他是不是第m个数,如果n*n枚举肯定炸,通过公式可知,函数跟j不是单调的关系,但跟i是单调的关系,所以每次枚举j,然后二分i的值,然后看前面有几个比第一个二分小的数,总的复杂度就是n*lgn*lgn。

小结:我一开始有个疑问,第2个二分判断的是前面有几个数比mid小,万一前面又m-1个数比他小,这样二分的这个数就是第m大了,可是如果这个mid并不在矩阵里咋办。。。其实第一个二分的跳出条件是num >= m,如果第一个二分枚举的mid 是第m大,return 0,然后mid变大,又在后面的区间二分,如果前面有m个数,但是这个数大于矩阵里的第m个数,mid就会变小,然后就不断逼近矩阵里的第m个数,l慢慢变大,r慢慢变小,最后一次是第二个二分返回m个数,并且最后一个数就是第一个二分的mid。。

#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>using namespace std;const int maxn = 5e4 + 5;typedef long long ll;ll n, m;ll cnt(ll i, ll j){    return i*i + 100000*i + j*j - 100000*j+i*j;}int check(ll x){    ll num = 0;    for(ll j = 1; j <= n; j++)    {        ll l = 1, r = n, mid, ans = 0;        while(l <= r)        {            mid = (l+r)/2;            if(cnt(mid, j) <= x)  //这里要有等号            {                ans = mid;                l = mid + 1;            }            else            {                r = mid - 1;            }        }        num += ans;        if(num >= m) return 1;  //这里也要有等号    }    return 0;}int main(){    int t;    scanf("%d", &t);    while(t--)    {        scanf("%lld%lld", &n, &m);        ll l = -(ll)100000*n, r = n*n+(ll)100000*n+n*n+n*n, mid, ans;        while(l <= r)        {            mid = (l+r)/2;            if(check(mid))            {                ans = mid;                r = mid - 1;            }            else                l = mid + 1;        }        PRintf("%lld/n", ans);    }    return 0;}


发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表