https://codeforces.com/contest/954/problem/E
题目大意
给出 $N (\le 2 \times 10 ^ 5)$ 个水龙头的水量 $a_i (\le 10 ^ 6)$ 和温度 $t_i (\le 10 ^ 6)$，每个水龙头可以取 $0 \sim a_i$ 的实数单位水量，问可以混合出 $T (\le 10 ^ 6)$ 温度的水最多多少。
若每个龙头取 $c_i$ 单位水，则混合水的温度为 $\frac{\sum c_i t_i)}{\sum c_i}$
简要题解
首先想到所有 $T$ 温度的水是都要的，然后想到离 $T$ 越近的水龙头越好，要优先选好的水龙头。
可以反证，假设 $T < t_i < t_j$，最优解中没有用完 $a_i$ 还有 $b_i$ 就选择了 $c_j$，则此时，我们总可以把 $\Delta = \min(b_i (t_i - T) / (t_j - T), c_j)$ 单位的 $j$ 换成 $\Delta (t_j - T) / (t_i - T)$ 单位的 $i$，显然这样的总水量会更大，矛盾。
这样我们从 $T$ 最近的位置维护两个指针，每次取这两个位置最多的使得混合温度是 $T$ 即可。
需要注意的点：
- 所有温度都高于或低于 $T$ 的话肯定只能混合出 $0$ 单位的水。
- 注意因为过程中需要用到 double，在计算过程中需要注意精度和类型转化。
复杂度
$T$：$O(N \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 double EPS = 1e-12;
typedef pair<int, double> PID;
void solve() {
int n, tar; cin >> n >> tar;
vector<int> a(n), t(n);
for (int& i : a) cin >> i;
for (int& i : t) cin >> i;
vector<PII> b;
for (int i = 0; i < n; i++) {
b.push_back({t[i], a[i]});
}
sort(b.begin(), b.end());
vector<PID> c;
for (int i = 0; i < n; i++) {
if (c.empty() || c.back().first != b[i].first) {
c.push_back(PID{b[i].first, b[i].second});
} else {
c.back().second += b[i].second;
}
}
n = c.size();
// for (auto [t, a] : c) {
// cerr << t << ' ' << a << '\n';
// }
// cerr << endl;
double ans = 0;
int p = lower_bound(c.begin(), c.end(), PID(tar, 0)) - c.begin();
if (p == n) {
cout << "0\n";
return;
}
int l = p - 1, r = p;
if (c[p].first == tar) {
ans += c[p].second;
r++;
}
double ll, rr;
if (0 <= l) {
ll = c[l].second;
}
if (r < n) {
rr = c[r].second;
}
while (0 <= l && r < n) {
// al * (tar - c[l].first) == ar * (c[r].first - tar)
double ratio = 1.0 * (tar - c[l].first) / (c[r].first - tar);
double diff = min(ll, rr / ratio);
ll -= diff;
rr -= diff * ratio;
ans += diff;
ans += diff * ratio;
if (ll <= EPS) {
l--;
if (l >= 0) {
ll = c[l].second;
}
}
if (rr <= EPS) {
r++;
if (r < n) {
rr = c[r].second;
}
}
}
cout << fixed << setprecision(10) << ans << '\n';
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: E. Cashback - Codeforces Round 466 (Div. 2)