bzoj 1492: [NOI2007]货币兑换Cash-白红宇

bzoj 1492: [NOI2007]货币兑换Cash

阅读量：5926 次

发布时间：2019-06-19

本文共 1412 字，大约阅读时间需要 4 分钟。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #define eps 1e-9 6 using namespace std; 7 #define M 100008 8 double f[M]; 9 struct data10 {11     double k,a,b,rate,x,y;12     int id;13 }q[M],t[M];14 int zhan[M],n;15 bool cmp(data a1,data a2)16 {17     return a1.k>a2.k;18 }19 double dp(int a1,int a2)20 {21     if(!a2)22       return -1e20;23     if(fabs(q[a1].x-q[a2].x)
         
          >1,l1=l,l2=mid+1;37     for(int i=l;i<=r;i++)38       if(q[i].id<=mid)39         t[l1++]=q[i];40       else41         t[l2++]=q[i];42     for(int i=l;i<=r;i++)43       q[i]=t[i];44     fen(l,mid);45     int t2=0;46     for(int i=l;i<=mid;i++)47       {48         for(;t2>1&&dp(zhan[t2-1],zhan[t2])
          
           q[i].k;)57 t1++;58 f[q[i].id]=max(f[q[i].id],q[zhan[t1]].x*q[i].a+q[zhan[t1]].y*q[i].b);59 }60 fen(mid+1,r);61 l1=l;62 l2=mid+1;63 for(int i=l;i<=r;i++)64 if(((q[l1].x
           
            
             
              r)&&l1<=mid)65 t[i]=q[l1++];66 else67 t[i]=q[l2++];68 for(int i=l;i<=r;i++)69 q[i]=t[i];70 return;71 }72 int main()73 {74 scanf("%d%lf",&n,&f[0]);75 for(int i=1;i<=n;i++)76 {77 scanf("%lf%lf%lf",&q[i].a,&q[i].b,&q[i].rate);78 q[i].id=i;79 q[i].k=-q[i].a/q[i].b;80 }81 sort(q+1,q+n+1,cmp);82 fen(1,n);83 printf("%.3lf",f[n]);84 return 0;85 }