[ABC312C] Invisible Hand

其他题解都是二分，这里介绍一种 \(O(n+m)\) 的线性写法。

我们尝试考虑在 \(x\) 为和值时会出现答案？

很显然，对于任意 \(1 \leq i \leq n\) 和 \(1 \leq j \leq m\)，\(x\) 只可能等于 \(a_i\) 或 \(a_i+1\) 或 \(b_i\) 或 \(b_i+1\)。即 \(x\) 为这 \(2 \times (n+m)\) 种情况中的一个。

如何证明呢？可以发现，如果我们想让卖家多一人，我们就将 \(x\) 调整为下一个 \(a_i\)；而想让买家少一人，我们就将 \(x\) 调整为下一个 \(b_j+1\)。而将 \(x\) 调整到其他数值，如果可以成立，则必有比它小的。

综上，我们只需依次枚举 \(x\)，在判断这种情况下合不合法即可。

代码如下。

#include <bits/stdc++.h>
using namespace std;
#define int long long
// head
const int N=2e5+5;
int a[N],b[N];
vector<int> all;
signed main() 
{
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	
	int n,m;cin>>n>>m;
	for(int i=0;i<n;i++) {cin>>a[i];all.push_back(a[i]);}
	for(int j=0;j<m;j++) {cin>>b[j];all.push_back(b[j]);}
	sort(all.begin(),all.end());
	sort(a,a+n);
	sort(b,b+m);
	int sum=0,now=0;
	int i=0,j=0;
	while(now<=n+m)
	{
		sum=V[now]; //枚举x
		while(i!=n&&a[i]<=sum)i++;
		while(j!=m&&b[j]<sum)j++;
		if(i>=m-j){ //是否成立
			cout<<sum<<endl;
			return 0;
		}
		sum=V[now]+1; //枚举 x
		while(i!=n&&a[i]<=sum)i++;
		while(j!=m&&b[j]<sum)j++;
		if(i>=m-j){ //是否成立
			cout<<sum<<endl;
			return 0;
		}
		now++;
	}
}