BZOJ 2726: [SDOI2012]任务安排 斜率优化 + 凸壳二分 + 卡精

Code:

#include<bits/stdc++.h>

#define setIO(s) freopen(s".in","r",stdin)

#define maxn 1000000

#define ll long long

#define ldb long double

using namespace std;

int n,s,head,tail;

int q[maxn];

ll f[maxn],sumt[maxn],sumf[maxn];

ldb x(int i) { return (ldb)1.000000*sumf[i]; }

ldb y(int i) { return (ldb)1.000000*f[i]; }

ldb slope(int i,int j) { return (ldb)(y(i)-y(j))/(ldb)(x(i)-x(j)); }

int main()

{

    int i,j;

    // setIO("input");

    scanf("%d%d",&n,&s);

    for(i=1;i<=n;++i)

    {

        scanf("%lld%lld",&sumt[i],&sumf[i]);

        sumt[i]+=sumt[i-1];

        sumf[i]+=sumf[i-1];

    }

    for(i=1;i<=n;++i)

    {

        int l=1,r=tail,re=0;

        while(l<=r)

        {

            int mid=(l+r)>>1;

            if(f[q[mid]]-f[q[mid-1]] < (sumt[i]+s)*(sumf[q[mid]]-sumf[q[mid-1]]))

                re=mid,l=mid+1;

            // if(slope(q[mid], q[mid-1])<sumt[i]+s)

            else r=mid-1;

        }

        f[i]=f[q[re]]-(sumt[i]+s)*(sumf[q[re]])+sumf[i]*sumt[i]+s*sumf[n];

        while(tail&&(f[q[tail]]-f[i])*(sumf[q[tail-1]]-sumf[i])<=(f[q[tail-1]]-f[i])*(sumf[q[tail]]-sumf[i]))--tail;

        q[++tail]=i;

    }

    printf("%lld\n",f[n]);

    return 0;

}