题意简述
- 给你 \(n\) 杯水，第 \(i\) 杯的水温为 \(t_i\)，容量为 \(v_i\)，依次倒入容量为 \(V\) 的大盆。注意每次倒入水后盆内水的总体积必须恒定为 \(V\)，且每杯水必须全部倒入，因此为防止倒进水时溢出，在倒水之前可以从盆里往外倒出一些水。求每次倒进水后盆里水温度的最大值（每次计算时情况独立
否则太简单了，不计倒水时的热损耗）。数据保证有解（即每次倒入水时总有办法使盆内水总体积为 \(V\)）。 - \(1\leq n\leq 5\times 10^5\),\(1\leq V\leq 10^9,0\leq t_i\leq 10^9(1\leq i\leq n),1\leq v_i\leq V(1\leq i\leq n,v_1=V)\)
题目分析
题意中既要按顺序倒入水又要倒出水，还要不停维护最大值，考虑到较大的数据范围，我们应使用单调队列进行求解。根据题意我们可以维护一些水的决策，具体每个决策有 \(v\)（体积）、\(t\)（温度） 两个属性值。
我们先考虑在“倒进”水之前要“倒出”的水决策。很明显它的 \(t\) 一定要尽可能低，否则倒出 \(t\) 更低的决策明显可以使总温度更高，因此更优。从而考虑维护 \(v\) 值单调递增的单调队列。每次“倒入”水（将当前决策入队）之前，为保持总体积恒定，根据“倒入”的水的 \(v\) 值不断“倒出”队头决策（出队），当队头决策无法完全“倒出”（即队头的 \(v\) 过大）时仅“倒出”一部分（保留队头决策，将它的 \(v\) 值减小一部分）。
然后我们再考虑倒入水的情况。首先将当前决策入队。由于当前决策的 \(t\) 值可能小于原来队尾决策的 \(t\) 值，违反了单调性，因此可以通过不停将原队尾与当前决策“混合”，降低队尾的 \(t\) 值，直到满足单调性为止。
值得一提的是，我们与其不断计算维护总温度值，不如利用物理学概念：热量 \(Q=mt\)（此题中是水，我们可以姑且认为 \(v\) 与 \(m\) 等价），这样每次混合水的时候，可以直接得出 \(Q'=Q_1+Q_2\)，\(v'=v_1+v_2\)，温度则只需要计算 \(t=\frac{Q}{m}\) （此题中也可以表示为\(t=\frac{Q}{v}\)），明显方便许多。
代码实现
#include<bits/stdc++.h>
using namespace std;
const double eps=1e-8;//避免浮点误差
int n,l=1/*队首*/,r/*队尾*/;
double V/*恒定总体积*/,q1[500010]/*单调队列中每个决策的体积*/,q2[500010]/*单调队列中每个决策的热量*/;
double del/*每次倒出的水*/,a1/*倒入水的温度*/,a2/*倒入水的体积*/,sm1/*总体积*/,sm2/*总热量*/;
int main()
{
scanf("%d%lf",&n,&V);
for(int i=1;i<=n;i++)
{
scanf("%lf%lf",&a1,&a2);
while(sm1+a2>V)//当前体积加上倒入水的体积大于恒定体积就倒出队头
{
del=min(q1[l],sm1+a2-V);//倒出队头，倒不完就只倒一部分
sm1-=del;//减去队头体积
sm2-=del*q2[l];//减去队头热量
q1[l]-=del;//队头体积减去倒掉的部分
if(fabs(q1[l])<eps)//如果队头倒没了就出队
l++;
}
q2[++r]=a1;
q1[r]=a2;//倒入水，入队
sm1+=a2;//更新体积
sm2+=a2*a1;//更新热量
while(l<r&&q2[r-1]>q2[r])//维护单调性
{
r--;
q2[r]=(q2[r]*q1[r]+q2[r+1]*q1[r+1])/(q1[r]+q1[r+1]);//混合后的队尾温度
q1[r]+=q1[r+1];//混合后的体积
}
printf("%.7lf\n",sm2/sm1);//热量÷质量（体积）=温度
}
return 0;
}