貼代碼博客……
#include <cstdio>#include <iostream>#include <algorithm>#include <cmath>#define N 100010#define inf 1<<30#define eps 1e-9using namespace std;int n,s,head,tail;int q[N];double f[N];struct days{ double a,b,r,x,y,k; int g; friend bool Operator <(days a,days b){ return a.x<b.x+eps||(fabs(a.x-b.x)<=eps&&a.y<b.y+eps); }}d[N],id[N],p[N];inline bool cmp(days a,days b){ return a.k<b.k;}inline double getk(int x,int y){ if(!x) return -inf; if(!y) return inf; if(fabs(p[x].x-p[y].x)<=eps) return -inf; return (p[x].y-p[y].y)/(p[x].x-p[y].x);}void solve(int l,int r){ int mid=l+r>>1,t1=l,t2=mid+1; if(l==r){ f[l]=max(f[l-1],f[l]); p[l].y=f[l]/(d[l].a*d[l].r+d[l].b); p[l].x=p[l].y*d[l].r; return; } for(int i=l;i<=r;i++) if(d[i].g<=mid) id[t1++]=d[i]; else id[t2++]=d[i]; for(int i=l;i<=r;i++) d[i]=id[i]; solve(l,mid); int head=1,tail=0; for(int i=l;i<=mid;i++){ while(head<tail&&getk(q[tail],q[tail-1])+eps<getk(i,q[tail])) tail--; q[++tail]=i; } for(int i=r;i>mid;i--){ while(head<tail&&d[i].k<getk(q[head],q[head+1])+eps) head++; f[d[i].g]=max(f[d[i].g],p[q[head]].x*d[i].a+p[q[head]].y*d[i].b); } solve(mid+1,r); t1=l,t2=mid+1; for(int i=l;i<=r;i++) if((p[t1]<p[t2]||t2>r)&&t1<=mid) id[i]=p[t1++]; else id[i]=p[t2++]; for(int i=l;i<=r;i++) p[i]=id[i];}int main(){ scanf("%d%d",&n,&s); f[0]=s; for(int i=1;i<=n;i++){ scanf("%lf%lf%lf",&d[i].a,&d[i].b,&d[i].r); d[i].k=-d[i].a/d[i].b; d[i].g=i; } sort(d+1,d+1+n,cmp); solve(1,n);新聞熱點
疑難解答
