题解 【AT2402 [ARC072D] Dam】
command_block
·
·
题解
题意 ： 有个水库，最多能存 L 单位水，一开始是空的。
接下来 n 天，第 i 天早上有 v_i 单位的，水温为 t_i 的水流入水库。
每天晚上你可以放掉一些水，多少自定，但必须保证第二天水库不会溢出。
现在问，对于每个 i ，在使用最优放水策略的情况下，第 i 天水库是满的情况下最高水温（每一问之间互相独立）。
------------
总水温 $=$ 各部分不同温度的水的 体积$\times$温度 的和除以总量 $L$。
我们称 体积$\times$温度 为“热量”。由于体积 $L$ 一定，我们只需要最大化热量。
记 $f[i][x]$ 表示第 $i$ 天晚上，若水库内只能保留 $x$ 升水，能获得的最大热量。
若将 $f[i][x]$ 视作函数 $f_i(x)$ ，观察其性质。
若存在一组方案，容量为 $x_0$ ，热量为 $w$ ，则单纯的倒水可以得到 $y=wx/x_0\ (x\in[0,x_0])$ 这个和原点相连的线段。
此外，水变多了热量不会变少。对于 $x\geq x_0$ ，$f_i(x)\geq w$。
于是，这个函数上的任意一点，向原点的连线下方不会有函数，水平向右发射的射线下方也不会有函数。不难发现，这必然是一个**上凸壳**。
接下来，考虑凸壳 $f_{i-1}(x)$ 的转移，如图 ：
转移无非两步，第一步强制加水，第二步任意倒水。第一步可以刻画为加一个向量，第二步则向原点连线并取 $\max$。
其中第二步需要找到移动后的凸壳上与原点相连斜率最大的点，然后将前面的线段去掉，并将该点和原点相连。
容易使用双端队列维护凸壳，队列中装的是向量，从左到右描述相邻两个顶点的差值。
- 将凸壳 $>L-v_i$ 的部分去掉。
- 将当前向量 $(v_i,t_i)$ 放到队头。
- 若队头的向量的斜率小于下一个向量，则将两者相加。这对应下面的过程。
不难发现，这可以实现我们想要的效果。
（需要维护各项量的和，以便回答询问）
复杂度 $O(n)$。
```cpp
#include<algorithm>
#include<cstdio>
#include<queue>
#define db double
#define MaxN 500500
using namespace std;
struct Point{db x,y;};
deque<Point> q;
int n,L;
int main()
{
scanf("%d%d",&n,&L);
db ans=0.0;
for (int i=1,u,v;i<=n;i++){
Point now;
scanf("%lf%lf",&now.y,&now.x);
now.y*=now.x;
db dx=now.x;
while(!q.empty()&&dx>1e-10)
if (dx>q.back().x+1e-10){
dx-=q.back().x;ans-=q.back().y;
q.pop_back();
}else {
q.back().y/=q.back().x;
ans-=q.back().y*dx;
q.back().y*=(q.back().x-=dx);
dx=0.0;
}
q.push_front(now);ans+=now.y;
while(q.size()>1&&q[0].y/q[0].x<q[1].y/q[1].x){
Point sav=q[0];q.pop_front();
q[0].x+=sav.x;q[0].y+=sav.y;
}printf("%.9f\n",ans/L);
}return 0;
}
```