首页 > 代码库 > POJ 3685 二分
POJ 3685 二分
Matrix
| Time Limit: 6000MS | Memory Limit: 65536K | |
| Total Submissions: 7034 | Accepted: 2071 |
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
Source
POJ Founder Monthly Contest – 2008.08.31, windy7926778
题意：
有n*n的矩阵，A(ij)的值是 i2 + 100000 × i + j2 - 100000 × j + i × j，求矩阵中第k小的数。
输入 t
输入t行n k
输出结果
代码：
//和上一题差不多，当j固定时表达式随i的增大而增大，先二分第k小数的值s，然后枚举j，//找小于等于s的i的个数有几个，用这个值与k比较来二分。#include<iostream>#include<cstdio>#include<cstring>using namespace std;typedef long long ll;int t;ll n,k;ll make(ll i,ll j){ return i*i+j*j+i*100000-j*100000+i*j;}bool solve(ll m){ ll cnt=0; for(int j=1;j<=n;j++){ int l=1,r=n,ans=0; while(l<=r){ int i=(l+r)>>1; if(make(i,j)<=m){ ans=i; l=i+1; }else r=i-1; } cnt+=ans; } return cnt>=k;}int main(){ scanf("%d",&t); while(t--){ scanf("%lld%lld",&n,&k); ll l=-100000*n; ll r=n*n+n*n+100000*n+n*n,ans; while(l<=r){ ll m=(l+r)>>1; if(solve(m)){ ans=m; r=m-1; }else l=m+1; } printf("%lld\n",ans); } return 0;}
POJ 3685 二分
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。