题目描述
有 $N$ 个任务排成一个序列在一台机器上等待执行,它们的顺序不得改变。
机器会把这 $N$ 个任务分成若干批,每一批包含连续的若干个任务。
从时刻 $0$ 开始,任务被分批加工,执行第 $i$ 个任务所需的时间是 $T_i$。
另外,在每批任务开始前,机器需要 $S$ 的启动时间,故执行一批任务所需的时间是启动时间 $S$ 加上每个任务所需时间之和。
一个任务执行后,将在机器中稍作等待,直至该批任务全部执行完毕。
也就是说,同一批任务将在同一时刻完成。
每个任务的费用是它的完成时刻乘以一个费用系数 $C_i$。
请为机器规划一个分组方案,使得总费用最小。
输入格式
第一行包含两个整数 $N$ 和 $S$。
接下来 $N$ 行每行有一对整数,分别为 $T_i$ 和 $C_i$,表示第 $i$ 个任务单独完成所需的时间 $T_i$ 及其费用系数 $C_i$。
输出格式
输出一个整数,表示最小总费用。
数据范围
$1 \le N \le 3 \times 10^5$,
$0 \le S,C_i \le 512$,
$-512 \le T_i \le 512$
输入样例:
5 1
1 3
3 2
4 3
2 3
1 4
输出样例:
153
C++ 代码
/*
同上一题相比,本题的区别在于 T[i] 可以取负数了(完成一个任务所需要的时间是负数,这是认真的吗?doge)
而因为这一点,本题用于平移的直线
斜率 k = (T[i] + S) 不再为正且单调递增了
截距 b = f[i] - T[i] * C[i] - S * C[n] 同样如此
不过本题虽然斜率不具有单调性,但是新加的点的横坐标具有单调性
不过本题依旧要我们求解最小花费,故仍可以沿用上一题的思路
经过上一题的洗礼,我们不难发现
最优的点 (C[i], f[i]) 是第一个大于当前平移直线斜率的点
故本题,查询时只能用二分
而插入时,仍可以按照原来的方法维护凸包, 凸包点集构成的斜率仍是单调递增的
*/
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 300010;
LL T[N], C[N];
LL f[N];
int q[N];
int n, S;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> S;
for(int i = 1;i <= n;++ i)
{
cin >> T[i] >> C[i];
T[i] += (LL)T[i - 1], C[i] += (LL)C[i - 1];
}
int hh = 0, tt = -1;
q[++ tt] = 0;
for(int 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]]) > (T[i] + S) * (C[q[mid + 1]] - C[q[mid]])) r = mid;
else l = mid + 1;
}
int j = q[r];
f[i] = f[j] + T[i] * C[i] - T[i] * C[j] + S * C[n] - S * C[j];
// 两个 long long 类型的数据相乘需要强制转换成 __int128,防止溢出
while(hh < tt && (__int128)(f[q[tt]] - f[q[tt - 1]]) * (C[i] - C[q[tt - 1]]) >= (__int128)(f[i] - f[q[tt - 1]]) * (C[q[tt]] - C[q[tt - 1]])) tt --;
q[++ tt] = i;
}
cout << f[n] << endl;
return 0;
}