有一个N阶方阵 第i行,j列的值Aij =i2 + 100000 × i + j2 - 100000 × j + i × j,需要找出这个方阵的第M小值.
Input
第一行输入T代表测试组数.
每个测试用例包含2个数字N,M表示在N阶方阵找出第M大值, N(1 ≤ N ≤ 50,000) and M(1 ≤ M≤ N × N). 每两个测试用例之间可能有空行
Output
输出方阵的第M小值
Sample Input
10 50000 2500000000 48888 2000000000 47777 1500000000 46666 1200000000 45555 1000000000 44444 900000000 43333 800000000 42222 700000000 41111 600000000 40000 500000000
Sample Output
7500000000 5129139981 3273537711 2261727633 1634929103 1368488613 1096871427 820144979 538443492 251994213
先二分答案也就是第M小的数 O(log(n^2+n*100000) )，然后在枚举每一列 O(n) ，再次使用二分计算当前列中小于等于 "第M小的数" 的元素的个数O(logn)。
第二次二分可行是因为 当j固定时A[i,j]是随 i 单增的。
#include<cstdio> #include<algorithm> using namespace std; #define ll long long ll n, m; ll cal(ll i,ll j){ return i*i+100000*i+j*j-100000*j+i*j; } bool valid(ll x){ ll cnt = 0,ans=0; for(ll j=1;j<=n;j++){ ll l = 1, r = n; while(l<=r){ ll mid = (l+r)/2; if(cal(mid,j)<=x) l = mid+1,ans=mid; else r = mid-1; } cnt += ans; } return cnt >= m; } int main(){ int t; scanf("%d",&t); while(t--){ scanf("%lld%lld",&n,&m); ll l = -n*100000, r = n*n+100000*n+5; while(l<=r){ ll mid = (l+r)/2; if(valid(mid)) r = mid-1; else l = mid+1; } printf("%lld\n",l); } return 0; }
原文：https://www.cnblogs.com/kongbb/p/10800214.html
