$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

思路：

1. 与 任务安排2 不同的地方是 t[i] + s 不再具有单调性
2. 凸包性质：相邻两点斜率单调递增，故可以用二分找到第一个大于 k 的斜率
3. 其他部分与 任务安排2 完全一致

可参考： 任务安排2

完整代码

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 300010;

int n,s;
LL t[N],c[N];
LL f[N];
int q[N];

int main()
{
    cin>>n>>s;

    for(int i=1;i<=n;i++)
    {
        cin>>t[i]>>c[i];
        t[i]+=t[i-1];
        c[i]+=c[i-1];
    }

    int hh=0,tt=0;
    for(int i=1;i<=n;i++)
    {
        //二分找第一个大于 k 的斜率
        int l=hh,r=tt;
        while(l<r)
        {
            int mid=l+r>>1;
            if(f[q[mid+1]]-f[q[mid]]>(t[i]+s)*(c[q[mid+1]]-c[q[mid]])) r=mid;
            else l=mid+1;
        }

        int j=q[r];
        f[i]=f[j]-c[j]*(t[i]+s)+t[i]*c[i]+s*c[n];
        while(hh<tt&&(double)(f[q[tt]]-f[q[tt-1]])*(c[i]-c[q[tt]])>=(double)(f[i]-f[q[tt]])*(c[q[tt]]-c[q[tt-1]])) tt--;
        q[++tt]=i;
    }

    cout<<f[n]<<endl;

    return 0;
}