D - Pairs 二分+二分

二分的一个小技巧
我们可以先把逻辑🔥大框架 写出来。像下面这样。
因为二分我们要先思考 我们要怎么拿到这个边界值。。
然后再去填充内部验证的逻辑细节。。这样写起来思路会清晰点。

内部就是分三类讨论。。也是单调的 所以再次二分 算个数。
因为i j 和j i 会被反复算。。我们这里没有规定方向。。所以要cnt/2

int a[N];
bool ok(int sum) {
	int cnt = 0;
      for(int i=1;i<=n;++i){
      	if(a[i]>0){};
      	if(a[i]=0){};
      	if(a[i]<0){};
      }

	return cnt >= sum;
};
void solve() {
	cin >> n >> k;
	for (int i = 1; i <= n; ++i)
		cin >> a[i];

	int l = -inf, r = inf;
	while (l < r) {
		int mid = (l + r + 1) >> 1;
		if (ok(mid))
			l = mid;
		else
			r = mid - 1;
	}
	cout << l;
};

然后这里写的二分竟然是左边界。。为啥啊

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll __int128_t
#define ar array<int, 2>
#define arr array<int, 3>
int  n, m, k, inf = 1LL << 61, mod = 998244353;// 1e9+7;
const int N = 5e5 + 50;
int a[N];
bool ok(int mx) {
	int cnt = 0;
	for (int i = 1; i <= n; ++i) {
		if (a[i] > 0) {
			if (a[i]*a[1] > mx)continue;
			int l = 1, r = n;
			while (l < r) {
				int mid = (l + r + 1) >> 1;
				if (a[mid]*a[i] <= mx)
					l = mid;
				else
					r = mid - 1;
			}
			cnt += l - (l >= i);
		};
		if (a[i] == 0) {
			if (mx >= 0)cnt += (n - 1);
		};
		if (a[i] < 0) {
			if (a[i]*a[n] > mx)continue;
			int l = 1, r = n;
			while (l < r) {
				int mid = (l + r) >> 1;
				if (a[mid]*a[i] <= mx)
					r = mid;
				else
					l = mid + 1;
			}
			cnt += n - l + 1 - (l <= i);
		};
	}

	return cnt / 2 >= k;
};
void solve() {
	cin >> n >> k;
	for (int i = 1; i <= n; ++i)
		cin >> a[i];
	sort(a + 1, a + n + 1);
	int l = -inf, r = inf;
	while (l < r) {
		int mid = (l + r) >> 1;//这边为什么是左边界。。？
		if (ok(mid))//数的是<=mid的个数。
			r = mid ;
		else
			l = mid + 1;
	}
	cout << l;
};



signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(15);
#ifdef DEBUG
	freopen("../1.in", "r", stdin);
#endif
	//init_f();
	//init();
	//expr();
	// int T; cin >> T; while(T--)
	solve();
	return 0;
}