首页 > 代码库 > poj3685(嵌套二分)
poj3685(嵌套二分)
Matrix
Time Limit: 6000MS | Memory Limit: 65536K | |
Total Submissions: 4658 | Accepted: 1189 |
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
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
Source
POJ Founder Monthly Contest – 2008.08.31, windy7926778
首先打个表看看,初步认为左下到右上递增。
认真一看,又不是特别有规律,在N比较大时候,递增就木有了。
但是每一列的单调性是可以保持的。这个分别将i,j看成常数求一下导数就非常容易知道了。
这个二分有意思。
在long long 范围内二分一个数X,>号即为 满足X大于矩阵的数大于等于M个
而大于矩阵的数的个数可以通过每一列二分来确定。
时间复杂度log(10^18)*N*log(N)。
#include <iostream> using namespace std; long long N, M; const long long INF = 1LL << 50; long long mtr ( long long i, long long j ) { return i * i + 100000 * i + j * j - 100000 * j + i * j; } bool b_s ( long long X ) { long long res = 0; for ( int i = 1; i <= N; i++ ) { int cnt = N ; int l = 1, r = N; while ( l <= r ) { int mid = ( r + l ) >> 1; if ( mtr ( mid, i ) >= X ) { r = mid - 1; cnt = mid - 1; } else { l = mid + 1; } } res += cnt ; } return res >= M; } int main() { int n; cin >> n ; while ( n-- ) { cin >> N >> M; long long l = -INF, r = INF; long long ans=-1; while ( l <= r ) { long long mid = ( r + l )>>1; if ( b_s ( mid ) ) { r = mid - 1; ans = mid - 1; } else { l = mid + 1; } } cout <<ans << endl; } return 0; }
poj3685(嵌套二分)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。