Time Limit: 6000MS | Memory Limit: 65536K | |
Total Submissions: 5489 | Accepted: 1511 |
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 10Sample Output
3-99993312100007-199987-99993100019200013-399969400031-99939题意:给了一个N*N的矩阵,每个位置上的数由该位置的下标i,j决定。然后问这个矩阵中第m小的数。
思路:第一个二分枚举答案,然后就要判断这个数前面有几个数,他是不是第m个数,如果n*n枚举肯定炸,通过公式可知,函数跟j不是单调的关系,但跟i是单调的关系,所以每次枚举j,然后二分i的值,然后看前面有几个比第一个二分小的数,总的复杂度就是n*lgn*lgn。
小结:我一开始有个疑问,第2个二分判断的是前面有几个数比mid小,万一前面又m-1个数比他小,这样二分的这个数就是第m大了,可是如果这个mid并不在矩阵里咋办。。。其实第一个二分的跳出条件是num >= m,如果第一个二分枚举的mid 是第m大,return 0,然后mid变大,又在后面的区间二分,如果前面有m个数,但是这个数大于矩阵里的第m个数,mid就会变小,然后就不断逼近矩阵里的第m个数,l慢慢变大,r慢慢变小,最后一次是第二个二分返回m个数,并且最后一个数就是第一个二分的mid。。
#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>using namespace std;const int maxn = 5e4 + 5;typedef long long ll;ll n, m;ll cnt(ll i, ll j){ return i*i + 100000*i + j*j - 100000*j+i*j;}int check(ll x){ ll num = 0; for(ll j = 1; j <= n; j++) { ll l = 1, r = n, mid, ans = 0; while(l <= r) { mid = (l+r)/2; if(cnt(mid, j) <= x) //这里要有等号 { ans = mid; l = mid + 1; } else { r = mid - 1; } } num += ans; if(num >= m) return 1; //这里也要有等号 } return 0;}int main(){ int t; scanf("%d", &t); while(t--) { scanf("%lld%lld", &n, &m); ll l = -(ll)100000*n, r = n*n+(ll)100000*n+n*n+n*n, mid, ans; while(l <= r) { mid = (l+r)/2; if(check(mid)) { ans = mid; r = mid - 1; } else l = mid + 1; } PRintf("%lld/n", ans); } return 0;}
新闻热点
疑难解答