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];//v t
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;
}