https://codeforces.com/contest/1251/problem/D
题目大意
给出奇数 $n \ (< 2 \times 10^5)$ 个人的薪资范围，其中第 $i$ 个人的范围为 $[l_i, r_i] (1 \le l_i \le r_i \le 10^9)$，以及薪资和的上限 $\sum l_i \le s \le 2 \times 10^{14}$。问当所有人的薪资 $x_i$ 符合自己的范围，且和不超过 $s$ 时，中位数最大可以是多少。
简要题解
乍一想因为我们有的是总薪资的上界，那么这个中位数大概是可以二分的。比如当某个方案中位数是 $x$ 则我们可以通过减少某些 $x$ 的值来得出对于 $x - 1$ 也成立。但是因为下限的存在 $x - 1$ 其实并不是总能达到的，因此我们选择更改一下二分的判断标准，即把二分判断改为，“当我们尝试将中位数设置到 $x$ 时，是否能得出不小于 $x$ 的中位数”。这样一来，就可以二分了。
另一种思考方式是，首先至少我们的中位数不会小于所有位置都选 $l_i$ 的结果 $x_0$，显然最优解如果 $x > x_0$ 一定在某些位置不是 $l_i$，且这些位置一定为 $x$。
判断的过程，对于每一个区间 $[l_i, r_i]$ 若其与 $x$ 不相交，则期望其与中位数无关，则对于它们都会取尽量小的 $l_i$ 使得其他区间有更多的操作空间。
- 如果我们有超过半数的区间已经严格小于 $x$ 则无论剩下的如何大，都不能使得中位数达到或超过 $x$。
- 若有超过半数的区间严格大于 $x$ 则显然我们已经得到了不差于 $x$ 的结果。
- 其他情况，说明有一些区间可以取到 $mid$，这里我们需要有足够多的值 $>= mid$ 而其他值尽量小，因此让 $l_i$ 最小的一些取 $l_i$ 即可。
复杂度
$T$：$O(n \log n \log \max(r_i))$
这里如果先把区间对所有 $l_i$ 排序可以去掉每次二分之后对 $l_i$ 的排序的 $\log n$
$S$：$O(n)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
const int INF = 1e9;
void solve() {
int n;
LL s;
cin >> n >> s;
vector<int> li(n), ri(n);
for (int i = 0; i < n; i++) {
cin >> li[i] >> ri[i];
}
auto check = [&](int mid) -> bool {
int cntless = 0, cntmore = 0;
LL sum = 0;
vector<int> left;
for (int i = 0; i < n; i++) {
if (ri[i] < mid) {
sum += li[i];
cntless++;
} else if (mid < li[i]) {
sum += li[i];
cntmore++;
} else {
left.push_back(li[i]);
}
}
if (cntless >= (n + 1) / 2) return false;
if (cntmore >= (n + 1) / 2) return true;
sort(left.begin(), left.end());
int need = n / 2 - cntless;
for (int i = 0; i < need; i++) {
sum += left[i];
}
sum += 1LL * (left.size() - need) * mid;
return sum <= s;
};
int l = 1, r = INF;
int ans = 1, mid;
while (l <= r) {
mid = (l + r) >> 1;
if (check(mid)) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
cout << ans << '\n';
}
int main() {
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: [CF] C. Minimize The Integer - Educational Codeforces Round 75 (Rated for Div. 2)