首页 > 代码库 > poj3685 Matrix 二分 函数单调性
poj3685 Matrix 二分 函数单调性
| Memory Limit: 65536K | ||
| Total Submissions: 4637 | Accepted: 1180 |
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
121 12 12 22 32 43 13 23 83 95 15 255 10
Sample Output
3-99993312100007-199987-99993100019200013-399969400031-99939
思路:
1 可以看出当j确定的时候i是单调递增的,那么就可以二分得到某个值当j确定时有多少i的值大于它,设为big
2 二分答案当big+ind>n*n(也即全部个数)时,这个值就太小了,增加下界,反之减少上界即可
错误原因 1:全部个数忘了n*n,打成n了 2:上下界错误,看成了1e4 3:读取爆longlong
#include <cstdio>using namespace std;long long ind,n;long long equ(long long i,long long j){ return i*i+j*j+i*j+(i-j)*100000;}long long judge(long long mid){ long long big=0; for(int j=1;j<=n;j++){ int l=0; int r=n+1; long long cp; while(r-l>1){ int m=(r+l)>>1; cp=equ(m,j); if(cp==mid){ l=m; break; } else if(cp<mid){ l=m; } else{ r=m; } } // printf("binary %I64d col %d %I64d\n",mid,j,l); big+=n-l; } return big;}void printe(){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ printf("%6I64d ",equ(i,j)); } puts(""); }}int main(){ int T; // freopen("C:\\Users\\Administrator\\Desktop\\input.txt","r",stdin); scanf("%d",&T); while(T--){ scanf("%I64d%I64d",&n,&ind); long long l=-(3*n*n+n*300000),r=-l; //printe(); while(r-l>1){ long long mid=l+r>>1; long long big=judge(mid); if(big>n*n-ind){ l=mid; } else { r=mid; } } printf("%I64d\n",r); } return 0;}
poj3685 Matrix 二分 函数单调性
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。