题目描述
题解
我们可以二分一个中位数，判断中位数是否大于等于这个数。
那么我们求得就是中位数大于等于这个数的最大值。
我们可以将大于等于mid的数字标记为1，其余的标记为0.
则最后的check是否合法都取决于最顶端的数字如何了。
我们会发现如果最中间有相邻两个格子是一样的，说明它们一定可以延续到最顶端。
否则就好考虑这种情况：
- 有相邻两个一样的
然后你可以发现边上如果有两个相邻的，会逐渐跳到中间。因此我们只需要从中间往边上扫，扫到的第一个存在相邻两个相同的就直接返回即可。 - 不存在相邻两个一样的。直接返回最边上的数字即可。
就这样，十分巧妙的将中位数问题转化为二分答案的判定问题。
#include <bits/stdc++.h>using namespace std;
const int N = 300000;int n;
int a[N], b[N];bool