1. ARC072F - Dam
发现当 \(t\) 递增时优先倒掉前面的，再选后面的；否则优先选后面的，再一起倒掉。所以维护单调队列中 \(t\) 递增，每次弹出队首 \(>L\) 的部分，然后插入队尾。若队尾 \(t_{i-1}>t_i\) 则将两个合并。
点击查看代码
//AT_arc072_d
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, L, v[N];
double t[N];
typedef long long ll;
pair<double, int> q[N];
int l = 1, r;
int main(){
scanf("%d%d", &n, &L);
for(int i = 1; i <= n; ++ i){
scanf("%lf%d", &t[i], &v[i]);
}
q[++r] = make_pair(t[1], v[1]);
double sum = t[1] * 1.0 * v[1];
printf("%.9lf\n", sum / L);
for(int i = 2; i <= n; ++ i){
int nw = v[i];
while(nw){
int mn = min(q[l].second, nw);
sum -= q[l].first * mn;
q[l].second -= mn;
nw -= mn;
if(!q[l].second){
++ l;
}
}
while(l <= r && q[r].first >= t[i]){
t[i] = (q[r].first * q[r].second + t[i] * v[i]) * 1.0 / (q[r].second + v[i]);
v[i] += q[r].second;
sum -= q[r].first * q[r].second;
-- r;
}
q[++r] = make_pair(t[i], v[i]);
sum += t[i] * 1.0 * v[i];
printf("%.9lf\n", sum / L);
}
return 0;
}