算法分析
由于题目问的是浓度第 $k$ 大的方案对应的浓度,满足二段性,所以我们可以考虑二分出这个值
假设答案为 $X$,则有 $\frac{A+C}{A+B+C+D} \geqslant X$
令 $B’ = A+B$,$D’ = C+D$,可以得到 $\frac{A+C}{B’+D’} \geqslant X$
$\frac{A+C}{B’+D’} \geqslant X \Leftrightarrow A+C \geqslant X(B’+D’) \Leftrightarrow A-B’X \geqslant D’X-C$
再令 $S_i = A-B’X$,$T_j = D’X-C$,可以得到 $S_i \geqslant T_j$
于是,我们只需在将 $S$ 和 $T$ 排序后,用双指针找到满足条件的 $j$ 的个数即可!
ps: 也可以参考神犇泥土笨笨的 题解
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
int main() {
int n, m; ll k;
cin >> n >> m >> k;
vector<int> a(n), b(n), c(m), d(m);
rep(i, n) cin >> a[i] >> b[i];
rep(i, m) cin >> c[i] >> d[i];
rep(i, n) b[i] += a[i];
rep(i, m) d[i] += c[i];
double ac = 0, wa = 1;
auto f = [&](double x) {
vector<double> s(n), t(m);
rep(i, n) s[i] = a[i]-b[i]*x;
rep(i, m) t[i] = d[i]*x-c[i];
sort(s.begin(), s.end());
sort(t.begin(), t.end());
int j = 0; ll res = 0;
rep(i, n) {
while (j < m and t[j] < s[i]) j++;
res += j;
}
return res;
};
rep(ti, 80) {
double wj = (ac+wa)/2;
if (f(wj) >= k) ac = wj; else wa = wj;
}
printf("%.10f\n", ac*100);
return 0;
}