poj3685 Matrix (二分套二分)
Matrix
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
思路:
二分第m大的数,但是check不好搞
可以发现当 j 固定的时候 i 越大数值越大,对于每一列 j 二分求出小于等于mid的数,累加起来
如果累加的和大于等于m则说明mid大于等于第k大
code:
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
ll n,m;
ll cal(ll i,ll j){//i大值大,j大值小
return i*i+100000*i+j*j-100000*j+i*j;
}
bool check(ll x){//判断x是否大于等于第m大
ll sum=0;//小于等于x的数的个数
for(int j=1;j<=n;j++){//求出每一列比x小的数的个数累加,结果就是矩阵中小于x的数的个数
int l=1,r=n;//二分枚举i
int ans=0;//每一列j固定,数值根据i递增
while(l<=r){
int mid=(l+r)/2;
if(cal(mid,j)<=x){
ans=mid;
l=mid+1;
}else{
r=mid-1;
}
}
sum+=ans;//累加上当前列小于等于x的数的个数
}
return sum>=m;//x是否大于等于第m大
}
signed main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%lld%lld",&n,&m);
ll l=cal(0,n),r=cal(n,0);
ll ans=0;
while(l<=r){
ll mid=(l+r)/2;
if(check(mid)){
ans=mid;
r=mid-1;
}else{
l=mid+1;
}
}
printf("%lld\n",ans);
}
return 0;
}
上一篇: 二分 River Hopscotch (poj 3258)
下一篇: C语言之二分查找