AcWing302 任务安排（二分维护斜率）

这道题因为斜率可能不是一直递增，所以要用二分来维护

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
using namespace std;
typedef long long ll;
const int N=3e5+10;
int q[N];
ll f[N];
ll st[N],sc[N];
int getup(int i,int j){
    return f[i]-f[j];
}
int getdown(int i,int j){
    return sc[i]-sc[j];
}
int main(){
    int n,s;
    cin>>n>>s;
    int i;
    for(i=1;i<=n;i++){
        scanf("%lld%lld",&st[i],&sc[i]);
        st[i]+=st[i-1];
        sc[i]+=sc[i-1];
    }
    int hh=0;
    int tt=0;
    q[0]=0;
    for(i=1;i<=n;i++){
        int l=hh,r=tt;
        while(l<r){
            int mid=l + r >>1;
            if((f[q[mid + 1]] - f[q[mid]]) > (st[i] + s) * (sc[q[mid + 1]] - sc[q[mid]]))
            r = mid;
            else l = mid + 1;
        }
        f[i] = f[q[l]] - (st[i] + s) * sc[q[l]] + sc[i] * st[i] + s * sc[n];
          while (hh < tt && (f[q[tt]] - f[q[tt - 1]]) * (sc[i] - sc[q[tt]]) >= (f[i] - f[q[tt]]) * (sc[q[tt]] - sc[q[tt - 1]])) 
            tt -- ;
        q[++tt]=i;
    }
    cout<<f[n]<<endl;
}