Description
有一坐体积为m的水库，每天早上会有水流进来，晚上会放水， 每天流进来的水的温度和体积都可能不同，俩温度不同的水混合后的温度为：
t1∗v1+t2∗v2v1+v2
t
1
∗
v
1
+
t
2
∗
v
2
v
1
+
v
2
， 假设水的温度不受其他因数影响，求第x天（x=1~n）中午水的温度最高多少（水库第x天的水必须是满的）。 当然要保证水库不会水太多爆炸。
Solution
如果每天流入的水的温度是递增的，那么显然是取最后m体积的水最优， 对于温度递增的入水，我们先放在一个队列中，不急着混合， 如果一个递增的入水队列，在放入了第i天的水后，温度不是递增的了，那么怎么办？ 因为第i天的水是必须要全部流进水库的，我们可以把第i天的水和当前队列尾的水混合，如还不是递增的，就一直混合队尾的两个水，直到满足温度递增的条件，
这个显然是正确的（想不到，真的想不到）
复杂度：
O(n)
O
(
n
)
Code
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
#define JS(q,w) ((d[q][0]*d[q][1]+d[w][0]*d[w][1])/(d[q][0]+d[w][0]))
#define SM(q) (d[q][0]*d[q][1])
using namespace std;
typedef double db;
const int N=
500500;
int read(
int &n)
{
char ch=
' ';
int q=
0,w=
1;
for(;(ch!=
'-')&&((ch<
'0')||(ch>
'9'));ch=getchar());
if(ch==
'-')w=-
1,ch=getchar();
for(;ch>=
'0' && ch<=
'9';ch=getchar())q=q*
10+ch-
48;n=q*w;
return n;
}
int m,n;
db ans;
db d[N][
2];
int main()
{
int q,w;
read(n),read(m);
int l=
1,r=
0,all=
0;
fo(i,
1,n)
{
read(q),read(w);
d[++r][
0]=w,d[r][
1]=q;ans+=SM(r);
all+=w;
for(;l<r&&d[r-
1][
1]>=d[r][
1];--r)
if(d[r-
1][
0]+d[r][
0]<=m)
{
ans-=SM(r)+SM(r-
1);
d[r-
1][
1]=JS(r-
1,r),d[r-
1][
0]+=d[r][
0];
ans+=SM(r-
1);
}
else
{
l=--r;
d[r][
0]=m-d[r+
1][
0];
d[r][
1]=JS(r,r+
1);
d[r][
0]=m;all=m;
ans=SM(r);
break;
}
for(;all>m;++l)
if(all-d[l][
0]>=m)ans-=SM(l),all-=d[l][
0];
else
{
ans-=SM(l);
d[l][
0]-=(all-m);
ans+=SM(l);all=m;
break;
}
printf(
"%.10lf\n",ans/m);
}
return 0;
}
