【AtCoder Regular Contest 072 F】Dam | Mrsrz's blog

单调队列。

题目大意：

有 $n$ 天，每天会有 $t_i$ 度，$V_i$ 升水加进来。

你有一个容量为 $L$ 的容器，每天必须接住所有 $V_i$ 升水。

现在问你，对于每个 $i$，求出第 $i$ 天水恰好是满的情况下的最高水温。

混合后的水温计算方法为：$t_3=\frac{t_1V_1+t_2V_2}{V_1+V_2}$

不考虑汽化。

题解：

根据生活常识，如果加进来高温的水，我们先把低温的倒掉一点好。如果加进来低温的水，我们加进来之后再倒掉好。

我们维护一个水温递增的单调队列，用来存储当前的水。

在没有任何修改的情况下，这些水的最终温度为它们直接合并起来的结果。

考虑新加入水，我们需要从队首把最冷的水倒掉。这样显然是优的。

如果新加入的水温度比队尾的水低，那么把它们混合起来。这样显然不会变劣。然后继续混合直到满足递增为止。

用一个变量存储当前队列的 $\sum_{i}{t_iV_i}$ 即可。

时间复杂度 $O(n)$。

Code：

#include<cstdio>
#include<utility>
const int N=5e5+6;
std::pair<double,int>q[N];
int n,L,dlt,H,T;long long v;
double all,t;
int main(){
    scanf("%d%d%lf%d",&n,&L,&t,&v);
    printf("%.13f\n",t);
    q[0]=std::make_pair(t,v);
    all=t*v;
    for(int i=2;i<=n;++i){
        scanf("%lf%lld",&t,&v);
        dlt=v;
        while(dlt)if(dlt<q[H].second)all-=q[H].first*dlt,q[H].second-=dlt,dlt=0;else
        all-=q[H].first*q[H].second,dlt-=q[H++].second;
        while(H<=T&&t<q[T].first)all-=q[T].first*q[T].second,t=(t*v+q[T].first*q[T].second)/(v+q[T].second),v+=q[T--].second;
        q[++T]=std::make_pair(t,v);
        all+=t*v;
        printf("%.13f\n",all/L);
    }
    return 0;
}