当前位置: 代码迷 >> 综合 >> POJ3685-二分套二分
  详细解决方案

POJ3685-二分套二分

热度:94   发布时间:2024-01-18 01:06:36.0

题意:给出一个矩阵的对应元素的计算公式,求第M小的元素的值是多少

题解:首先二分答案,如果对应这个答案,比该答案小的元素个数大于M个, 则在左区间继续二分,否则在右区间二分

            在统计元素个数的过程中,还会在用到一次二分,我们在枚举j的过程中,每当j固定以后,函数就是关于i的单调递增函数,因此可以二分求得i为多少时该函数的值小于之前二分的答案,并计算小于M的元素个数

#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std ;
long long N , M ;
long long fun(long long i , long long j)
{return i * i + 100000 * i + j * j - 100000 * j + i * j ;
}
long long judge(long long x)
{long long cnt = 0 ;long long j , l , r , mid ;for(int j = 1 ; j <= N ; j ++){l = 1 ;r = N + 1 ;mid = (l + r ) >> 1 ;while(l < r){if(fun(mid , j) >= x) r = mid ;else l = mid +1;mid = (l + r) >> 1 ;}cnt += mid - 1 ;}return cnt ;
}
int main()
{int T ;scanf("%d" , &T) ;while(T --){scanf("%lld%lld" , &N , &M) ;long long ll , rr , mmid , cnt ;ll = -1e12 ;rr = 1e12 ;mmid = (ll + rr) >> 1 ;while(ll < rr){if(judge(mmid) >= M) rr = mmid ;else ll = mmid + 1 ;mmid = (ll + rr) >> 1 ;}printf("%lld\n", mmid -1);}return 0;
}