斜率优化(CDQ分治)：BZOJ 1492: [NOI2007]货币兑换Cash

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <algorithm>
 5 using namespace std;
 6 const double eps=1e-8;
 7 const int maxn=100010;
 8 struct Node{
 9     double a,b,r,x,y,k;
10     int id;
11 }d[maxn],t[maxn];
12 double f[maxn];
13 int st[maxn],cnt,n;
14 double Abs(double a){return a>0?a:-a;}
15 double K(int a,int b){
16     if(Abs(d[a].x-d[b].x)<eps)return 1e20;
17     return (d[a].y-d[b].y)/(d[a].x-d[b].x);
18 }
19 void Solve(int l,int r){
20     if(l==r){
21         f[l]=max(f[l],f[l-1]);
22         d[l].y=f[l]/(d[l].r*d[l].a+d[l].b);
23         d[l].x=d[l].y*d[l].r;
24         return;
25     }
26     int mid=(l+r)>>1,t1=l,t2=mid+1;
27     for(int i=l;i<=r;i++){
28         if(d[i].id<=mid)
29             t[t1++]=d[i];
30         else 
31             t[t2++]=d[i];
32     }
33     for(int i=l;i<=r;i++)d[i]=t[i];
34     Solve(l,mid);
35     cnt=0;
36     for(int i=l;i<=mid;i++){
37         while(cnt>1&&K(i,st[cnt])-K(st[cnt],st[cnt-1])>=eps)cnt--;
38         st[++cnt]=i;
39     }
40     int fir=1;
41     for(int i=mid+1;i<=r;i++){
42         while(fir<cnt&&K(st[fir+1],st[fir])-d[i].k>=eps)fir++;
43         f[d[i].id]=max(f[d[i].id],d[st[fir]].x*d[i].a+d[st[fir]].y*d[i].b);
44     }
45     Solve(mid+1,r);
46     t1=l;t2=mid+1;
47     for(int i=l;i<=r;i++){
48         if(t2==r+1||(d[t2].x-d[t1].x>=eps||Abs(d[t2].x-d[t1].x)<eps&&d[t2].y-d[t1].y>=eps)&&t1<=mid)
49             t[i]=d[t1++];
50         else    
51             t[i]=d[t2++];
52     }    
53     for(int i=l;i<=r;i++)
54         d[i]=t[i];
55 }
56 
57 
58 bool cmp(Node a,Node b){
59     return a.k>b.k;
60 }
61 int main(){
62     scanf("%d%lf",&n,&f[1]);
63     for(int i=1;i<=n;i++){
64         scanf("%lf%lf%lf",&d[i].a,&d[i].b,&d[i].r);
65         d[i].k=-d[i].a/d[i].b;
66         d[i].id=i;
67     }
68     sort(d+1,d+n+1,cmp);
69     Solve(1,n);
70     printf("%.3lf\n",f[n]);
71     return 0;
72 }