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

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

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\n",ans);}
}

?