传送门

写了一个DP,用二进制分组维护凸包来转移,结果爆精度了。。。

然后卡了半天也卡不过去,无奈去看了题解,发现直接维护凸包就行了。。。题解的思路就是把当前体积看成横坐标,体积乘以水温看成纵坐标,这样的话加水就是向量加法,放水就是向量乘以一个$[0,1]$之间的实数。容易发现每天可以达到的状态一定构成一个包含原点的凸包,每天的操作相当于把这个凸包向右上方平移一下之后再加入原点,以及把凸包右边导致下一步溢出的部分切掉。由于我们求的是横坐标为$V$时纵坐标的最大值,直接维护上凸包就行了。由于横坐标都是整数,所以就不存在爆精度的问题啦~

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#define MAXN 500010
#define LL long long
using namespace std;

const long double eps=1e-8;

int n;
LL V,px[MAXN];
long double py[MAXN];
pair<LL,long double> Q[MAXN];
int head=1,tail=1;

long double getK(pair<LL,long double> t1,pair<LL,long double> t2){
    return (t2.second-t1.second)/(t2.first-t1.first);
}

void insert(LL x,long double y){
    pair<LL,long double> pt(x,y);
    while(tail-head>=1 && getK(pt,Q[tail])<getK(Q[tail],Q[tail-1])) Q[tail--];
    Q[++tail]=pt;
}

void cut(LL x){
    while(Q[head].first>x){
        pair<LL,long double> temp=Q[head++];
        if(Q[head].first<x){
            long double ty=Q[head].second+getK(Q[head],temp)*(x-Q[head].first);
            Q[--head]=make_pair(x,ty);
        }
    }
}

int main(){
#ifdef DEBUG
    freopen("F.in","r",stdin);
#endif
    scanf("%d%d",&n,&V);
    for(int i=1;i<=n;i++){
        double temp;
        scanf("%lf%d",&temp,px+i);
        py[i]=temp*px[i];
    }
    Q[1]=make_pair(0,0);
    for(int i=1;i<=n;i++){
        cut(Q[tail].first+V-px[i]);
        insert(Q[tail].first-px[i],Q[tail].second-py[i]);
        double ans=(Q[head].second-Q[tail].second)/V;
        printf("%.7lf\n",ans);
    }
}