Descriptions
有一个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
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
题目链接
https://vjudge.net/problem/POJ-3685
在main函数中
设mid为N阶方阵中第sum小的数，若sum<M，则mid小了
若sum>M，则mid大了
在judge函数中
(mid,j)即为(i,j)，一列一列的找有mid个数比value小，再把每一列的mid加一起，即可得出在N阶方阵中比value小的数的个数sum
AC代码
#include <iostream> #include <cstdio> #include <fstream> #include <algorithm> #include <cmath> #include <deque> #include <vector> #include <queue> #include <string> #include <cstring> #include <map> #include <stack> #include <set> #include <sstream> #define IOS ios_base::sync_with_stdio(0); cin.tie(0); #define Mod 1000000007 #define eps 1e-6 #define ll long long #define INF 0x3f3f3f3f #define MEM(x,y) memset(x,y,sizeof(x)) #define Maxn 100000+5 using namespace std; ll T,n,m; ll fun(ll i,ll j)//求值 { return i*i+100000*i+j*j-j*100000+i*j; } ll judge(ll value) { ll l,r,mid,sum; sum=0; for(ll j=1;j<=n;j++) { l=0,r=n+1; while(r-l>1) { mid=(l+r)/2; if(fun(mid,j)<value) l=mid; else r=mid; } sum+=l; } return sum; } int main() { scanf("%lld",&T); while(T--) { scanf("%lld",&n); scanf("%lld",&m); ll l,r,mid; l=-1e12,r=1e12;//设置上下界 while(r-l>1) { mid=(l+r)/2; if(judge(mid)<m) l=mid; else r=mid; } printf("%lld\n",l); } return 0; }
原文：https://www.cnblogs.com/sky-stars/p/11317502.html