题目
C - Invisible Hand
思路
- 二分X，同时二分得到buyer和seller的人数（很精巧的二分~）；
- 当然，从复杂度角度，\(O(N\log N)\) 也是可以的；
- 实际上可以写成\(O(N)\)的形式？感觉线性扫描也可？
代码
点击查看代码
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
using LL = long long;
using PII = pair<int, int>;
const int N = 2e5 + 10;
int a[N], b[N];
void solv()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i ++) cin >> a[i]; // sell
for (int i = 1; i <= m; i ++) cin >> b[i]; // buy
sort(a + 1, a + 1 + n);
sort(b + 1, b + 1 + m);
int l = 0, r = 1e9 + 10;
while (l < r)
{
int mid = (l + r ) / 2;
int isell = upper_bound(a + 1, a + 1 + n, mid) - a;
int nsell = isell - 1; // 最低售价 >= mid 的 sellers 的人数
int ibuy = lower_bound(b + 1, b + 1 + m, mid) - b;
int nbuy = m - ibuy + 1; // 最高出价 <= mid 的 buyers 的人数
if (nsell >= nbuy) r = mid;
else l = mid + 1;
}
cout << l << endl;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int T = 1;
// cin >> T;
while (T --)
{
solv();
}
return 0;
}