任务安排3

AcWing-302-任务安排3

分析

见《进阶指南》第326页。

实现

#include <iostream>
#include <cstring>
using namespace std;

typedef long long LL;
const int N = 300010;
int n, s;
int h = 1, t, q[N];
LL st[N], sc[N];
double f[N]; // 数据爆 long long

int binary_search (int k) {
    int l = h, r = t;
    while (l < r) {
        int mid = l + r >> 1;
        if (f[q[mid + 1]] - f[q[mid]] <= k * (sc[q[mid + 1]] - sc[q[mid]]))
            l = mid + 1;
        else
            r = mid;
    }
    return q[l];
}

int main () {
    scanf("%d%d", &n, &s);
    for (int i = 1, t, c; i <= n; ++ i) {
        scanf("%d%d", &t, &c);
        st[i] = st[i - 1] + t;
        sc[i] = sc[i - 1] + c;
    }

    memset(f, 0x3f, sizeof(f));
    f[0] = 0;
    q[++ t] = 0;
    for (int i = 1; i <= n; ++ i) {
        int ptr = binary_search(s + st[i]);
        f[i] = f[ptr] - (s + st[i]) * sc[ptr] + st[i] * sc[i] + s * sc[n];
        while (h < t
            && (f[q[t]] - f[q[t - 1]]) * (sc[i] - sc[q[t]])
            >= (f[i] - f[q[t]]) * (sc[q[t]] - sc[q[t - 1]])
        ) {
            -- t;
        }
        q[++ t] = i;
    }
    printf("%.0lf", f[n]);
    return 0;
}