Matrix POJ - 3685(二分套二分)
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作比较,然后不断的去更新答案。
代码如下:
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
ll n,m;
inline ll fun(ll i,ll j)
{
return (i*i+j*j+i*j+100000*(i-j));
}
inline ll solve(int pos,ll x)
{
int l=1,r=n,mid,ans=0;
while(l<=r)
{
mid=l+r>>1;
if(fun(mid*1ll,pos*1ll)<=x)
{
ans=mid;
l=mid+1;
}
else r=mid-1;
}
return ans;
}
inline bool judge(ll x)
{
ll sum=0;
for(int i=1;i<=n;i++)
sum+=solve(i,x);
return sum<m;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%lld%lld",&n,&m);
ll l=-1e10,r=1e10,mid;
ll ans=l;
while(l<=r)
{
mid=l+r>>1;
if(judge(mid))
{
ans=mid;
l=mid+1;
}
else r=mid-1;
}
printf("%lld\n",ans+1);
}
return 0;
}
努力加油a啊,(o)/~
上一篇: 算法学习笔记——二分
下一篇: java中同步和异步有什么异同?
推荐阅读
-
POJ 2942Knights of the Round Table(tarjan求点双+二分图染色)
-
POJ1743 Musical Theme(后缀数组 二分)
-
POJ 1358 Housing Complexes G++ 二分图匹配 没掌握
-
POJ 1719 Shooting Contest G++ 二分图匹配 没掌握
-
poj 2728 Desert King(最小比率生成树 / 0-1分数规划 / 二分)
-
[POJ](1631)Bridging signals ---- LIS+O(nlogn)优化(二分)
-
POJ 3692 Kindergarten(挑战程序设计竞赛,二分图最大团)
-
O - Steady Cow Assignment POJ - 3189(二分 + 多重匹配)
-
M - Jamie‘s Contact Groups POJ - 2289(二分 + 多重匹配)
-
POJ 2456: Aggressive cows(二分,贪心)