题解 AT4867 【[ABC155D] Pairs】

~~这其实是一篇求助帖~~ 要求出第k小的乘积，有负数有正数，不太好处理，于是不难想到二分答案，所以问题转化成给定一个k，求出有多少对数的乘积$\leq mid$ 我们分两类类讨论： $Case1:$ 如果我们二分的值$x>=0$，所有乘积$<=0$的数对全部成立，那么任意负数与正数都成立，任意的0与所有非零数都成立，所有0内部组合也成立 然后我们考虑乘积大于0的。枚举每一个数，那么合法的另一个数的取值一定是在一段区间，二分找到端点就可以了。 $Case2:$ 对于所有$x<0$的二分值，一定是需要一个负数乘以一个正数，也可以用二分来找到对应合法区间 总复杂度$O(N*log_2N*log_2{10^{18}})$，其实二分值域以后内部可以用双指针来实现，复杂度为$O(N*log_2{10^{18}})$。 ~~好的回归正题，这是一篇求助帖：~~ 为什么$lower$_$bound$不加一些边界处理会有问题啊？（见代码打注释的那两行） ### $Code:$ ``` #include<bits/stdc++.h> using namespace std; #define il inline #define re register #define int long long #define D double il int read() { re int x = 0, f = 1; re char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar(); return x * f; } #define rep(i , a , b) for(int i = (a) , i##Limit = (b) ; i <= i##Limit ; ++ i) #define maxn 200005 int n, m, a[maxn], ans, Mi = -1e18, Ma = 1e18, c1, c2, b[maxn], c[maxn], g, d[maxn], c3; il int check(int x) { int tem = 0; if(x >= 0) { tem = g * (c1 + c2) + g * (g - 1) / 2 + c1 * c2; rep(i, 1, c1 - 1) tem += upper_bound(b + i + 1, b + c1 + 1, x / b[i]) - b - 1 - i; rep(i, 1, c2 - 1) tem += upper_bound(c + i + 1, c + c2 + 1, x / c[i]) - c - 1 - i; } else { x = -x; rep(i, 1, c1){ int pos = lower_bound(c + 1, c + c2 + 1, (int)ceil((D)x / (D)b[i])) - c; ////对就是这两行 if(b[i] * c[pos] < x) pos++; if(b[i] * c[pos - 1] >= x) -- pos; ////对就是这两行 if(c2 >= pos) tem += c2 - pos + 1; } } return tem >= m; } signed main() { n = read(), m = read(); rep(i, 1, n) a[i] = read(); rep(i, 1, n) { if(a[i] < 0) b[++ c1] = -a[i]; else if(a[i] > 0) c[++ c2] = a[i]; else ++ g; } sort(b + 1, b + c1 + 1), sort(c + 1, c + c2 + 1); while(Mi < Ma){ int Mid = (Mi + Ma) >> 1; if(check(Mid)) Ma = Mid; else Mi = Mid + 1; } cout << Ma; return 0; } ```