题解 【AT2402 [ARC072D] Dam】

**题意** ： 有个水库，最多能存 $L$ 单位水，一开始是空的。 接下来 $n$ 天，第 $i$ 天早上有 $v_i$ 单位的，水温为 $t_i$ 的水流入水库。 每天晚上你可以放掉一些水，多少自定，但必须保证第二天水库不会溢出。 现在问，对于每个 $i$ ，在使用最优放水策略的情况下，第 $i$ 天水库是满的情况下最高水温（每一问之间互相独立）。 $n \leq 5 * 10^5$，时限$\texttt{2s}$。 ------------ 总水温 $=$ 各部分不同温度的水的 体积$\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; } ```