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;
}