[ABC312C] Invisible Hand

ziyistudy · 2023-12-18 22:13:05 · 题解

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

我们尝试考虑在 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++;
    }
}