题目链接： 点我 题目大意： 一个按照特殊算法计算的矩阵，求出矩阵中第m小的数字。 题目分析： 矩阵很大，不能把矩阵中所有的数算出来（废话），不难发现，当j不变的时候，值随i的增大而增大，所以矩阵的每一列都是递增的。用二分列举X，再用二分计算X在每列中有多个数字小于等于X就可以判断X是大了还是小了。 PS ：所有数据全部使用 long long 就不会出错了
Problem: 3685 User: ChenyangDu Memory: 152K Time: 1282MS Language: C++ Result: Accepted #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> typedef long long ll; using namespace std; const ll INF = 100000000000; long long T,n,m; ll get(ll j,ll i){ return (i*i + 100000 * i + j*j - 100000 * j + i *j); } long long C(ll x){ //计算有多少比X小的数 long long ans = 0; for(long long i=1;i<=n;i++){ long long l = 0,r = n+1; //[0,n+1) while(l<r-1){ long long mid = (l+r)>>1; if(get(i,mid)>x)r = mid; else l = mid; } ans += l; } return ans; } int main(){ //freopen("in.txt","r",stdin); scanf("%lld",&T); while(T--){ scanf("%lld%lld",&n,&m); ll l = -INF,r = INF; while(l<r-1){ ll mid = (l+r)>>1; if(C(mid) >= m)r = mid; else l = mid; } printf("%lld\n",r); } return 0; }