二分-poj-3685-Matrix
题目链接：
http://poj.org/problem?id=3685
题目大意：
有n*n的矩阵，第i行第j列的数为Aij= i2 + 100000 × i + j2 - 100000 × j + i × j,求矩阵中第k小的数。
解题思路：
显然每一列是单调的，二分答案，枚举每一列，再二分行标，求出该列能够满足的个数，从而找到矩阵不超过他的个数。
代码：
#include<iostream>#include<cmath>#include<cstdio>#include<cstdlib>#include<string>#include<cstring>#include<algorithm>#include<vector>#include<map>#include<set>#include<stack>#include<list>#include<queue>#include<ctime>#include<bitset>#define eps 1e-6#define INF 0x3f3f3f3f#define PI acos(-1.0)#define ll __int64#define lson l,m,(rt<<1)#define rson m+1,r,(rt<<1)|1#pragma comment(linker, "/STACK:1024000000,1024000000")using namespace std;#define Maxn 51000ll Cal(ll i,ll j){ return i*i+100000*i+j*j-100000*j+i*j;}int main(){ int t; ll n,m; scanf("%d",&t); while(t--) { scanf("%I64d%I64d",&n,&m); ll l=-10000000000000LL,r=1000000000000000LL; ll mid,ans; while(l<=r) { mid=(l+r)>>1; ll num=0; for(int col=1;col<=n;col++) //枚举每一列 { ll LL=1,rr=n,mmid; ll tmp=0; while(LL<=rr) { mmid=(LL+rr)>>1; ll res=Cal(mmid,col); if(res<=mid) { tmp=mmid; LL=mmid+1; } else rr=mmid-1; } num+=tmp; //求出该列小于等于mid的个数 } if(num<m) { l=mid+1; } else //注意最小的那个数就是恰好的第k小的那个，因为再比他小的话，肯定没有k个 { ans=mid; r=mid-1; } } printf("%I64d\n",ans); } return 0;}