51Nod-1288 汽油补给 ST表 贪心 模拟

51Nod-1288 汽油补给 ST表 贪心 模拟

题意

有(N+1)个城市，(0)是起点(N)是终点，开车从(0)依次到(N)，车每走一单位消耗一单位汽油。

给出两个城市的距离和当地的油价。求完整整个旅途最少的费用。

如果无法达到终点输出(-1)。

第一行给出(N)和(T)表示最大的汽油载油量。

[2 leq N leq 10^5 \ 1leq T leq 10^9 ]

分析

显然我们希望补给的油价越便宜越好，但是路线已经规定，我们希望下一次补给的越便宜越好。

贪心的想法就是在这里补好油刚刚好足够到下一个更加便宜的油的地方。

这样显然可以利用单调栈(O(N))维护。问题在于由于油量限制，有可能油量不足够到下一个地点。那么就需要继续贪心到这段区间里油量最便宜的位置。这里可以用ST表(O(NlogN))维护

实现的时候要注意很多细节.比如单调栈最后记得弹出栈.ST表的意义有所不同,变成了记录下标.

代码

int lg[maxn];
int f[maxn][21];
int nxt[maxn];
int a[maxn];
ll d[maxn];
int n;
stack<int> st;

void pre() {
    lg[1] = 0;
    lg[2] = 1;
    for (int i = 3; i < maxn; i++)
        lg[i] = lg[i >> 1] + 1;
    for (int i = 1; i <= n; i++)
        f[i][0] = i;
    for (int j = 1; j <= 21; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
            f[i][j] = (a[f[i][j - 1]] < a[f[i + (1 << (j - 1))][j - 1]]) ? f[i][j - 1] : f[i + (1 << (j - 1))][j - 1];
    for (int i = 1; i <= n; i++)
        nxt[i] = INF;
    for (int i = 1; i <= n; i++) {
        while (!st.empty() && a[i] < a[st.top()]) {
            nxt[st.top()] = i;
            st.pop();
        }
        st.push(i);
    }
    while (!st.empty()) nxt[st.top()] = n + 1, st.pop();
}

int query(int x, int y) {
    int s = lg[y - x + 1];
    return a[f[x][s]] < a[f[y - (1 << s) + 1][s]] ? f[x][s] : f[y - (1 << s) + 1][s];
}


int main() {
    n = readint();
    int T = readint();
    int flag = 1;
    for (int i = 1; i <= n; i++) {
        int tmp = readint();
        if (tmp > T) flag = 0;
        a[i] = readint();
        d[i + 1] = d[i] + tmp;
    }
    if (!flag) {
        puts("-1");
        return 0;
    }
    pre();
    ll res = 0;
    ll cur = 0;
    int x = 1, r = 1;
    while (x <= n) {
        while (d[r + 1] - d[x] <= T) r++;
        if (nxt[x] <= r) {
            int y = nxt[x];
            if (cur < d[y] - d[x]) res += a[x] * (d[y] - d[x] - cur);
            cur = 0;
            x = nxt[x];
        }
        else {
            int y = query(x + 1, r);
            res += a[x] * (T - cur);
            cur = T - (d[y] - d[x]);
            x = y;
        }
    }
    Put(res);
}