| Time Limit: 6000MS | Memory Limit: 65536K | |
| Total Submissions: 5724 | Accepted: 1606 |
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
12
1 1
2 1
2 2
2 3
2 4
3 1
3 2
3 8
3 9
5 1
5 25
5 10
Sample Output
3
-99993
3
12
100007
-199987
-99993
100019
200013
-399969
400031
-99939
Source
2.这个地方r不能初始化为n，因为假设
//n个数全是<x的话,按理讲应该sum+=n的，但是最后r-1之后sum+=(n-1)了，
//这是因为v(n,j)>x和v(n,j)=x的效果是不同的，假设v(n,j)>x的话,r仍然为n+1,而当v(n,j)=x话,sum+=n-1,r更新为n
#include<cstdio>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
using namespace std;
#define MM(a) memset(a,0,sizeof(a))
typedef long long LL;
typedef unsigned long long ULL;
const int mod = 1000000007;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f;
long long mid,l,r,n,m;
long long v(long long i,long long j)
{
return i*i+100000*i+j*j-100000*j+i*j;
}
long long ok(long long x)
{
long long sum=0;
for(long long j=1;j<=n;j++)
{
long long l=0,r=n+1;
while(r-l>1)
{
long long mid=(l+r)>>1;
if(v(mid,j)>=x)
r=mid;
else
l=mid;
}
sum+=(r-1);
}
return sum;
}
int main()
{
int cas;
scanf("%d",&cas);
while(cas--)
{
scanf("%lld %lld",&n,&m);
r=1e12;l=-1e12;
while(r-l>1)
{
mid=(l+r)>>1;
if(ok(mid)>=m)
r=mid;
else
l=mid;
}
printf("%lld\n",r-1);
}
return 0;
}
原文：http://www.cnblogs.com/smilesundream/p/5122960.html