题面

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

有一个$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;
}