python/TangDou/AcWing/ConvexHullTrick/301.cpp

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 300010;
LL t[N], c[N], f[N];
int q[N];

int main() {
    int n, s;
    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++) {
        /*
        Q:为什么是 hh < tt ?
        A:队列中最少有两个元素，才能考虑计算斜率，才能开始出队头
        队列中一个元素,hh=0,tt=0
        队列中两个元素,hh=0,tt=1 这样的情况下，保证了最少有一条边，才有斜率概念

        (1) k=st[i]+S 所有数据是正数，所以k是单调递增的
        (2) k从下向上移动，找到与点集的第一个交点，必然在下凸壳上
        (3) 在相交时，其实是与三个点组成的两条直线进行相交，设 a,b,c，能够相交的必要因素是K_{a,b}<k<K_{b,c}
        (4) 双向队列其实是一个单调上升的队列
        (5) 双向队列中只保留斜率比当前ki大的下凸壳点集，比ki斜率小的点，以后也不会再使用，在i入队列前，删除掉
        */

        // 队列头中的q[hh]其实是就是优解j,使得截距f[i]的值最小
        // 要保证随时从队列头中取得的数，是下凸壳中第一个从k=st[i]+s大的,原来有比k小于等于的点都可以剔除了
        while (hh < tt && f[q[hh + 1]] - f[q[hh]] <= (t[i] + s) * (c[q[hh + 1]] - c[q[hh]])) hh++;

        // Q:为什么在未入队列前更新？
        // A: 因为i是在查询它的前序j,找到了使它最小的j就对了，现在队列头中保存的就是使i最小的前序j,当然是放入队列前进行更新
        f[i] = f[q[hh]] - (t[i] + s) * c[q[hh]] + c[i] * t[i] + s * c[n]; // 利用公式更新最优解

        // 出队尾:现在凸包里记载的两个点之间斜率大于新加入值的清理掉
        while (hh < tt && (f[q[tt]] - f[q[tt - 1]]) * (c[i] - c[q[tt]]) >= (f[i] - f[q[tt]]) * (c[q[tt]] - c[q[tt - 1]])) tt--;
        q[++tt] = i;
    }
    // 输出
    cout << f[n] << endl;
    return 0;
}