最近在补全提高课所有题目的题解，宣传一下汇总的地方提高课题解补全计划

题目描述

给定一个 环，环 上有 $n$ 个节点，编号从 $1 \sim n$，以及一辆小车车

每一个 节点 $i$ 有一个 权值 $p_i$ 表示当车 到达该点 时，可以 获得 的 油量

还有一个 权值 $d_i$ 表示当车从 节点 $i$ 到 节点 $i+1$ 所需要 消耗 的 油量

现有一辆车想从环上 任意点 出发，顺时针 或 逆时针 绕环一圈走回起点

行驶的过程中，油量不能为 负数，初始油量 为 起点 处所能获得的 油量

判断能否完成 环圈行驶

分析

看到 环形问题，就会想到在先前 环形区间DP 中提到的一个解决方法：拉环成链

复制 一份数组接在 原数组 后面，这样原问题就 等价于 在 新数组 中 存在 长度为 $n + 1$ 的 合法区间

然后考虑区间何时 合法 的问题，题中提及：

1. 会先在一个点 获得油量
2. 然后 消耗油量 到达下一个点
3. 消耗后的油量 不能小于 0

这极像一个我们熟悉的 括号序列模型 — 任意 前缀区间 必然满足 左括号数$\ge$右括号数

故想到用 前缀和思想 来分析：该 区间 如果 合法，则必然 任意前缀 获得油量 $\ge$ 消耗油量

这里我们要 明确 每个数组下标的实际含义，才能调对本题的 边界，不然会 WA 疯

先讨论 顺时针的走法

1. $d[i]$：点 $i \rightarrow$ 点 $i+1$ 消耗 的 油量
2. $p[i]$：到点 $i$ 能 获得 的 油量

相对应的 前缀和 含义：

1. $sd[i]~(d[1 \cdots i])$：从 $1$ 出发到 $i+1$ 所 消耗 的 总油量
2. $sp[i]~(p[1 \cdots i])$：从 $1$ 出发到 $i$ 所 获得 的 总油量

显然，我们要到 $i+1$ 点，需要满足 此前的剩余油量 + 该点获得的油量 $\ge$ 到达下点消耗的油量

因此，我们直接 比较 相同下标下的前缀和大小 即可

$i$ 到 $i+n$ 的耗油：$d[i] + d[i + 1] + \cdots + d[i + n - 1]$
$i$ 到 $i+n$ 的加油：$p[i] + p[i + 1] + \cdots + p[i + n - 1]$

闫氏DP分析法

状态表示-集合 $f_i$：以 $i$ 为 起点 和 终点，顺时针 走一圈的 方案

状态表示-属性 $f_i$：方案 是否可行 $true$

状态计算 ：

$$ f_i = \bigg[\min\Big\{(sp_j - sp_{i-1}) - (sd_j - sd_{i-1})\Big\} \ge 0 \bigg] \quad (i \le j \le i+n-1) $$

和往常一样，提出 常量 ：$f_i = \bigg[sd_{i - 1} - sp_{i-1} + \min\Big\{sp_j - sd_j\Big\} \ge 0 \bigg] \quad (i \le j \le i+n-1)$

这样就变成一个 滑动窗口求最小值 的问题了，直接套 单调队列 即可

再推导一下滑动窗口的范围：$1 \le i + n - j \le n$

故 滑动窗口 满足的 最大大小 为 $n$，且 先算后加

再讨论 逆时针的走法

镜像分析 一下就好了，不过下标有所变化

大家可以先 平移下标，继续 套上述公式；也可以 再重新推导一遍，强化一下自己对公式推导的能力

我这里就 重新推导 一遍了

$i + n$ 到 $i$ 的耗油：$d[i] + d[i + 1] + \cdots + d[i + n - 1]$
$i + n$ 到 $i$ 的加油：$p[i + 1] + p[i + 2] + \cdots + p[i + n]$

闫氏DP分析法

状态表示-集合 $f_i$：以 $i$ 为 起点 和 终点，逆时针 走一圈的 方案

状态表示-属性 $f_i$：方案 是否可行 $true$

状态计算 ：

$$ f_i = \bigg[\min\Big\{(sp_{i+n} - sp_{j-1}) - (sd_{i+n-1} - sd_{j-2})\Big\} \ge 0 \bigg] \quad (i + 1 \le j \le i+n) \\\\ f_i = \bigg[sp_{i+n} - sd_{i+n-1} + \min\Big\{-sp_{j-1} + sd_{j-2}\Big\} \ge 0 \bigg] \quad (1 \le j - i \le n) $$

Code

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1e6 + 10, M = N << 1;

int n;
int p[M], d[M], que[M];
LL sp[M], sd[M];
bool f[N];

LL g(int j)
{
    return sp[j] - sd[j];
}
LL h(int j)
{
    return sd[j - 2] - sp[j - 1];
}
LL get_val1(int i, int j)
{
    return sd[i - 1] - sp[i - 1] + g(j);
}
LL get_val2(int i, int j)
{
    return sp[i + n] - sd[i + n - 1] + h(j);
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%d%d", &p[i], &d[i]);
        p[i + n] = p[i];
        d[i + n] = d[i];
    }
    for (int i = 1; i <= n << 1; i ++ )
    {
        sd[i] = sd[i - 1] + d[i];
        sp[i] = sp[i - 1] + p[i];
    }

    int hh = 0, tt = -1;
    for (int i = 1; i <= n << 1; i ++ )
    {
        while (hh <= tt && i - que[hh] > n) hh ++ ;
        if (i > n)
            if (get_val1(i - n, que[hh]) >= 0)
                f[i - n] = true;
        while (hh <= tt && g(que[tt]) >= g(i)) tt -- ;
        que[ ++ tt] = i;
    }

    hh = 0, tt = -1;
    for (int i = n << 1; i; i -- )
    {
        while (hh <= tt && que[hh] - i > n) hh ++ ;
        if (i <= n)
            if (get_val2(i, que[hh]) >= 0)
                f[i] = true;
        while (hh <= tt && h(que[tt]) >= h(i)) tt -- ;
        que[ ++ tt] = i;
    }
    for (int i = 1; i <= n; i ++ )
        puts(f[i] ? "TAK" : "NIE");
    return 0;
}