[BZOJ1492][NOI2007] 货币兑换 Cash

    题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1492

    题解：根据提示，必然存在一种最优的买卖方案满足：每次买进操作使用完所有的人民币，每次卖出操作卖出所有的金券。显然，对于每个状态，我们只需要记录该状态下的金券等值于多少人民币即可，而不需要记录AB券分别有多少种。

    设\(f_i\)代表第i天所持金券所等值的人民币的最大额，\(x_i,y_i\)表示对应的A券与B券数量，则显然有\(x_i=\frac{rate_i}{a_i rate_i + b_i}f_i,y_i=\frac{1}{a_i rate_i + b_i}f_i\)，状态转移方程为：\[f_i=max(x_j a_i + y_j b_i)\]

    这是一个标准的斜率优化的式子，变形为\(y_j=-\frac{a_i}{b_i}x_j+\frac{f_i}{b_i}\)。由于\(-\frac{a_i}{b_i}\)不单调，而且\(x_j,y_j\)也不单调，所以维护需要平衡树。平衡树实现相对会麻烦很多，这个时候cdq分治就很好用。先将所有点按照\(-\frac{a_i}{b_i}\)，再分治处理，将\(id<=mid\)的点放在左边，其余放在右边，且两边各自保持原来的相对顺序，就可以用左边的信息去更新右边的信息了。

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
const double eps=1e-9;
 
struct Info
{
    int id;
    double x,y;
    double a,b,rate,k;
}tmp[maxn];
 
bool cmpk(const Info &a,const Info &b) {return a.k>b.k;}
bool cmpx(const Info &a,const Info &b) {return a.x<b.x || (fabs(a.x-b.x)<eps && a.y<b.y);}
double Slope(const Info &a,const Info &b) {if (fabs(a.x-b.x)<eps) return 1e100;return (a.y-b.y)/(a.x-b.x);}
 
Info a[maxn];
double f[maxn];
int n;
 
int q[maxn];
void Update(int l,int r,int mid)
{
    int top=0,tail=0;
    q[0]=0;
    for (int i=l;i<=mid;i++)
    {
        while (top<tail && Slope(a[i],a[q[tail]])>Slope(a[q[tail]],a[q[tail-1]])) tail--;
        q[++tail]=i;
    }
    for (int i=mid+1;i<=r;i++)
    {
        while (top<tail && Slope(a[q[top]],a[q[top+1]])>a[i].k) top++;
        f[a[i].id]=max(f[a[i].id],a[q[top]].x*a[i].a+a[q[top]].y*a[i].b);
    }
}
 
void CDQ_Solve(int l,int r)
{
    if (l==r)
    {
        f[l]=max(f[l],f[l-1]);
        a[l].y=f[l]/(a[l].a*a[l].rate+a[l].b);
        a[l].x=a[l].y*a[l].rate;
        return;
    }
    int mid=(l+r)>>1;
    int p1=l,p2=mid+1;
    for (int i=l;i<=r;i++) (a[i].id<=mid)?tmp[p1++]=a[i]:tmp[p2++]=a[i];
    for (int i=l;i<=r;i++) a[i]=tmp[i];
    CDQ_Solve(l,mid);
    Update(l,r,mid);
    CDQ_Solve(mid+1,r);
    p1=l,p2=mid+1;
    for (int i=l;i<=r;i++) ((p1<=mid && cmpx(a[p1],a[p2])) || p2>r)?tmp[i]=a[p1++]:tmp[i]=a[p2++];
    for (int i=l;i<=r;i++) a[i]=tmp[i];
}
 
int main()
{
    scanf("%d%lf",&n,&f[0]);
    for (int i=1;i<=n;i++) scanf("%lf%lf%lf",&a[i].a,&a[i].b,&a[i].rate),a[i].id=i,a[i].k=-a[i].a/a[i].b;
    sort(a+1,a+1+n,cmpk);
    CDQ_Solve(1,n);
    printf("%.3f\n",f[n]);
    return 0;
}