题面

大秦为你打开题目传送门 （看不懂就看下面吧）

有一个$N× N$ 的矩阵

第 $i$ 行第 $j$ 列的值为 $𝑖^2 +100000× 𝑖 + 𝑗^2 −100000× 𝑗 + 𝑖 × 𝑗$

求矩阵中第 $M$ 小的数。

题意

二分第 $M$ 小的数，然后 $check$ 时枚举 $i$ ，再二分找小于 $mid$ 的数字，加起来看看是不是 $M$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

int n;
ll m;

void Input(){
	scanf("%d%lld", &n, &m);
}

ll Calc(ll i, ll j, ll x){
	if(i==n+1) return max(x, -x)+1;
	if(i==0) return min(x, -x)-1;
	return i*i+100000*i+j*j-100000*j+i*j;
}

bool Check(ll x){
	ll tot=0;
	for(int j=1; j<=n; j++){
		int l=0, r=n+1, best=-1;
		while(l<=r){
			int mid=(l+r)/2;
			if(Calc(mid, j, x)<x){
				l=mid+1;
				best=mid;
			}else{
				r=mid-1;
			}
		}
		tot+=best;
	}
	return tot<m;
}

void Work(){
	ll l=-1e10, r=1e10, best=-1;
	while(l<=r){
		ll mid=(l+r)/2;
		if(Check(mid)){
			l=mid+1;
			best=mid;
		}else{
			r=mid-1;
		}
	}
	printf("%lld\n", best);
}

int main(){
	int T;
	scanf("%d", &T);
	while(T--){
		Input();
		Work();
	}
	return 0;
}