poj 3685 二分

Matrix
Time Limit: 6000MS   Memory Limit: 65536K
Total Submissions: 7415   Accepted: 2197

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

题意:
n*n的矩阵,矩阵中的元素a[i,j]是 i*i+j*j+i*j+1e5*(i-j) ,求矩阵中的第m小的数
代码:
//首先二分答案mid,然后在矩阵中找小于mid的个数和m比较,i*i+j*j+i*j+1e5*(i-j) 是关于i递增的即矩阵的每一列都是递增的,
//所以可以枚举列数二分行数来找。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const ll qq=;
ll t,n,m;
ll solve(ll p)
{
ll sum=;
for(ll j=;j<=n;j++){
ll l=,r=n,ans=;
while(l<=r){
ll i=(l+r)>>;
if((i*i+j*j+i*j+qq*(i-j))<p) { ans=i;l=i+; }
else r=i-;
}
sum+=ans;
}
return sum;
}
int main()
{
scanf("%lld",&t);
while(t--){
scanf("%lld%lld",&n,&m);
ll l=-1e13,r=1e13,ans;
while(l<=r){
ll mid=(l+r)>>;
ll tmp=solve(mid);
if(tmp<=m-) { ans=mid;l=mid+; }
else r=mid-;
}
printf("%lld\n",ans);
}
return ;
}
上一篇:AngularJs练习Demo2


下一篇:使用AngularJS实现的前后端分离的数据交互过程