poj3685 二分套二分

F - 二分二分

Crawling in process... Crawling failed Time Limit:6000MS Memory Limit:65536KB 64bit IO Format:%lld & %llu

Submit Status

Description

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

Sample Output

3
-99993
3
12
100007
-199987
-99993
100019
200013
-399969
400031
-99939
题目大意：给你一个n*n矩阵，每一个位置都有一个值，这个值由该点的该点的行列标决定，问你第m小的元素是多少。
思路分析：比赛时都贴上二分标签了，最后还没敲出来，首次我们要二分答案，然后check，check函数里面按列
进行枚举，因为在j确定的情况下函数关于i递增，然后直接二分查找刚好小于等于mid的元素在每一列的位置，累加
return，判断返回的数与m的关系，继续二分
代码：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int inf=1e9;
typedef long long ll;
const int  C=100000;
ll f(ll x,ll y)
{
    return (x*x+C*x+y*y-C*y+x*y);
}
ll n,m;
ll checknum(ll num)
{
    ll cnt=0;
     for(int i=1;i<=n;i++)//枚举列，因为在列数确定的情况下表达式关于i是递增的
     {
            ll sl=1,sr=n;
            int ant=0;
            while(sl<=sr)
            {
                ll smid=(sl+sr)>>1;
                if(f(smid,i)<=num)
                {
                    ant=smid;
                    sl=smid+1;
                }
                else sr=smid-1;
            }
            cnt+=ant;
    }
    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+n*n;
       ll ans;
       while(l<=r)
       {
           ll mid=(l+r)>>1;
            //cout<<mid<<endl;
           if(checknum(mid)>=m)
           {
               ans=mid;
               //cout<<ans<<endl;
               r=mid-1;
           }
           else l=mid+1;
          // cout<<ans<<endl;
       }
       printf("%lld
",ans);
   }
}