如题：http://poj.org/problem?id=3685
| Time Limit: 6000MS | Memory Limit: 65536K | |
| Total Submissions: 5289 | Accepted: 1440 |
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 -99993 3 12 100007 -199987 -99993 100019 200013 -399969 400031 -99939
Source
思路：最先先到的是二分x，C（x）：小于x的元素个数是否<m .如何实现C（x）？问题肯定在条件上，i2 + 100000 × i + j2 - 100000 × j + i × j,这是每一个元素的值，分别对于i，j求偏导，发现关于i个偏导恒>0，因此在一列中，行数越大，值越大，因此对于所有列二分x，累加找出了小于<m的个数。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define ll _int64
ll getx(ll i,ll j)
{
return i*i+100000*i+j*j-100000*j+i*j;
}
int C(ll x,ll n,ll m) //在所有咧中，小于x的元素个数是否<m
{
ll i;
ll cnt=0;
for(i=1;i<=n;i++)
{
ll l=0,r=n+1;
while(r-l>1)
{
int mid=(l+r)/2;
if(getx(mid,i)>=x)
r=mid;
else
l=mid;
}
cnt+=l;
}
return cnt<m;
}
int main()
{
//freopen("C:\\1.txt","r",stdin);
int t;
ll n,m;
cin>>t;
while(t--)
{
scanf("%I64d%I64d",&n,&m);
ll l=-100000*n,r=n*n+100000*n+n*n+n*n;
while(r-l>1)
{
ll mid=(l+r)/2;
if(C(mid,n,m))
l=mid;
else
r=mid;
}
printf("%I64d\n",l);
}
return 0;
}