二分求操作后的最大最小中位数

这类题是让你求对序列进行一系列操作之后的最小/最大中位数

求最小中位数

二分最小中位数，显然二分要符合 mid 越大越对，边界才能向下收缩。

对于这个条件，我们选择计算 小于等于 当前 mid 的数才是对的，因为这样显然 mid 越大 cnt 越大，而符合这个条件，我们就不断收缩上界，直到达到第一个 (cnt \ge \frac{(n + 1)} 2) 的值为止，第一个大于等于就是等于，也就是 (cnt = \frac{n + 1}{2})，正好就是要的中位数。

1
2
3
4
5
6
7
8
9
10
11
12
auto check = [&](const int mid) {
    //小于等于当前mid的数 cnt >= (n + 1) / 2
		//进行一系列操作，统计操作后小于等于当前mid的个数
    
  	for(auto& ai : a) {cnt += ai <= mid;}
  
    return cnt >= (n + 1) / 2;
};

int lo{}, hi{(int)1E9}; while (lo <= hi) {
    int mid{(int)(lo + hi >> 1)}; check(mid) ? hi = mid - 1 : lo = mid + 1;
}

求最大中位数

那么就是要符合 mid 越小越对，边界才能向上收缩。

对于这个条件，我们选择计算 大于等于 当前 mid 的数才是对的，因为这样显然 mid 越小 cnt 越小，而符合这个条件，我们就不断收缩下界，直到达到第一个 (cnt \ge \frac{(n + 1)} 2) 的值为止，第一个大于等于就是等于，也就是 (cnt = \frac{n + 1}{2})，正好就是要的中位数。

1
2
3
4
5
6
7
8
9
10
11
12
auto check = [&](const int mid) {
    //大于等于当前mid的数 cnt >= (n + 1) / 2
		//进行一系列操作，统计操作后小于等于当前mid的个数
    
  	for(auto& ai : a) {cnt += ai <= mid;}
  
    return cnt >= (n + 1) / 2;
};

int lo{}, hi{(int)1E9}; while (lo <= hi) {
    int mid{(int)(lo + hi >> 1)}; check(mid) ? hi = mid - 1 : lo = mid + 1;
}