洛谷 P3422 分析（别看）

科技起源的小号1

2026-09-07 20:32:12

发布于：天津

0阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：所有可能情况的合法性

1.2 题目背景、允许、禁止与限制

背景：
有 $n$ 个空间站位于一个圆上
每个空间站都有一个可以为你补给的油量 $p_i$ （以“升”为单位）和到下一个空间站的距离 $d_i$ （每 $1$ 单位长度要用 $1$ 升油）
允许：
检查所有的 $n$ 个空间站：若从当前空间站出发以顺时针或逆时针可以走完一圈（也就是到达每个空间站时的油量始终 $\ge0$ ）（这里注意，题目中的“但是如果走到某个时候突然没油了那么旅行便失败了”代表只要全程 $\ge 0$ ，到达空间站可以立即加油，因此是 $\ge$ 而非 $>$ ）
求每个空间站的合法状态

1.3 题目数据范围与猜测

$3 \le n \le 10^6 \longrightarrow O(n)$

1.4 一句话概括题意

有 $n$ 个点成环形结构
每个点 $i$ 都有两个信息 $p_i$ 和 $d_i$ 表示可以为你补充的油量以及从 $i$ 到第 $i+1$ 个空间站所需消耗的油量
对于所有点 $i\in n$ ：若从 $i$ 出发以顺时针或逆时针可以走完一圈（也就是到达每个空间站时的油量始终 $\ge0$ ）则判断当前点合法
最终求每个点的合法状态

2 题目破题推导

2.1 第一步：大拆小，小组大

第一步：巧妙利用 $p_i$ 和 $d_i$
计算每一站的 $p_i-d_i$ ，相当于“净赚油量”
如果这个数是负数，代表到达下一站需要消耗之前剩下的油量
如果这个数是 $0$ ，代表到达下一站不会改变油量的状态
如果这个数是整数，代表到达下一站可以为之后存一些
第二步：拆分
我们遇到环，就考虑“破环成链”
也就是：
先将这道题给出的环形结构（ $n$ 个点的一个圆）转化为长度为 $2n$ 的一个链；这个链是： $1\rightarrow 2 \rightarrow \cdots \rightarrow n-1 \rightarrow n \rightarrow 1\rightarrow 2 \rightarrow \cdots \rightarrow n-1 \rightarrow n$
然后将这道题给出的“走一圈”（先不考虑正逆）转化为在一个起点沿一个固定方向走 $n$ 个点

2.2 第二步：以终为始以始为终

最终要求的答案是：从某一个点 $i(1\le i \le n)$ 开始走 $n$ 站会不会出现没油的情况
那么我们想：
成功条件是：全程油量 $\ge0$
相当于从某一个点 $i(1\le i \le n)$ 开始走 $n$ 站这一段中不会出现油量 $<$ 开始油量的情况
相当于从某一个点 $i(1\le i \le n)$ 开始走 $n$ 站这一段中的最小油量 $\ge$ 开始油量的情况

2.3 第三步：正向思维转逆向思维

到这一步基本都思考完毕
现在就差逆时针没考虑了
我们只需要将顺时针的链反过来就是逆时针链了
但是要注意，这时就变成了的 $p_1 - d_n$ 因为相当于从 $1\rightarrow 2$ 变成 $1\rightarrow n$ ，其他同理
而且原始编号也有变化

如果起始位置是 $1$ ，那么对应原编号就是 $1$
如果起始位置不是 $1$ ，那么对应原编号就是 $n-起始位置编号+2$

然后把这个答案映射到正确答案位置上

3 模型匹配

求固定长度区间最小值 $\rightarrow$ 滑动窗口
因为这里我们的起始点可能并不是1号点，所以要减去1号点到起始点这一段的油量，那这一段的油量怎么快速计算呢或者怎么优化呢？就是前缀和

4 最终代码（禁止抄袭，仅用于参考）

#include <bits/stdc++.h>
using namespace std;
#define int long long

int n;
const int N = 2e6 + 10;
int p[N], d[N];
int s1[N], s2[N];
int c1[N], c2[N];
int head = 0, tail = -1;
int q[N];
bool ans[N];

signed main(){

    cin >> n;
    for (int i = 1;i <= n;i++){
        cin >> p[i] >> d[i];
    }
    for (int i = 1;i <= n;i++){
        c1[i] = p[i] - d[i];
        c1[i + n] = c1[i];
    }
    for (int i = 1;i <= 2 * n;i++){
        s1[i] = s1[i - 1] + c1[i];
    }
    for (int i = 1;i <= 2 * n;i++){
        while(head <= tail && s1[q[tail]] >= s1[i]){
            tail--;
        }
        q[++tail] = i;
        if (i - q[head] + 1 > n){//
            head++;
        }
        if (i >= n){
            if (s1[q[head]] >= s1[i - n]){
                ans[i - n + 1] = true;
            }
        }
    }
    c2[1] = c2[n + 1] = p[1] - d[n];//
    for (int i = 2;i <= n;i++){
        c2[i] = p[n - i + 2] - d[n - i + 1];
        c2[i + n] = c2[i];
    }
    for (int i = 1;i <= 2 * n;i++){
        s2[i] = s2[i - 1] + c2[i];
    }
    head = 0, tail = -1;
    for (int i = 1;i <= 2 * n;i++){
        while(head <= tail && s2[q[tail]] >= s2[i]){
            tail--;
        }
        q[++tail] = i;
        if (i - q[head] + 1 > n){//
            head++;
        }
        if (i >= n){
            int startidx = i - n + 1;
            if (s2[q[head]] >= s2[startidx - 1]){
                if (startidx == 1){
                    ans[1] = true;
                } else {
                    ans[n - startidx + 2] = true;
                }
            }
        }
    }
    for (int i = 1;i <= n;i++){
        cout << (ans[i] ? "TAK\n" : "NIE\n");
    }
    
    return 0;
}