题意

有一些卖家，每个人愿意用大于等于 $a_i$ 的价格出售苹果。

还有一些买家，每个人愿意用小于等于 $b_i$ 的价格购买苹果。

现在要求你给定苹果的价格，满足愿意出售的人大于等于愿意购买的人的情况下，苹果的价钱尽量小。

思路

很显然的一道二分答案，由于我们不需要考虑人选的方案，只需考虑有多少人愿意卖或买，所以可以直接对 $a$ 数组和 $b$ 数组进行排序。

而后二分答案，每次用 $mid$ 在 $a$ 和 $b$ 数组中记录出有多少人，由于数组已经排序，所以这个可以使用 lower_bound 和 upper_bound 函数去查找有多少人在苹果价钱为 $mid$ 的情况下愿意买或卖。

因为当 $mid$ 越大时，愿意买的人越少，卖的人越多，所以满足单调性，可以二分。

至于为什么要使用 upper_bound，显然，如果我们在判断有多少人愿意买的时候只是用 lower_bound，那如果 $a$ 数组中不含 $mid$，那么 lower_bound 会查找到大于等于 $mid$ 的第一个数，其下标设为 $k$，那么愿意买的人就为 $k-1$，但如果 $a$ 含有 $mid$，则会找到 $mid$ 本身的下标，最后愿意买的人为 $k$，所以不妨直接使用 upper_bound，这样最后愿意买的人数都为 $k-1$。

注意 $1 \le a_i,b_i \le 10^9$，赛时死磕半天没看出来哪错了，结果…是因为 $r$ 的初始值开小了，开成 $10^9+100$ 即可，警钟长鸣。

代码

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
#include<bits/stdc++.h>
#define int long long
#define endl "\n" 
using namespace std;
template<typename P>
inline void read(P &x){
   	P res=0,f=1;
   	char ch=getchar();
   	while(ch<'0' || ch>'9'){
   		if(ch=='-') f=-1;
   		ch=getchar();
   	}
   	while(ch>='0' && ch<='9'){
   		res=res*10+ch-'0';
   		ch=getchar();
	}
	x=res*f;
}
int n,m;
int a[200010];
int b[200010];
bool check(int x){
	int sel=upper_bound(a+1,a+n+1,x)-a-1;
	int bou=m-(lower_bound(b+1,b+m+1,x)-b)+1;
	if(sel>=bou) return 0;
	return 1;
}
signed main(){
	read(n),read(m);
	for(int i=1;i<=n;++i) read(a[i]);
	for(int i=1;i<=m;++i) read(b[i]);
	sort(a+1,a+n+1);
	sort(b+1,b+m+1);
	int l=0,r=1e9+100,ans=0;
	while(l<=r){
		int mid=(l+r)>>1;
		if(check(mid)) l=mid+1;
		else r=mid-1,ans=mid;
	};
	cout<<ans<<endl;
	return 0;
}