旅行问题

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1970 字
环形公路n站，每站有油量p_i与到下一站距离
一本通
例
正文

/*
原题：T1600 「一本通 5.5 例 4」旅行问题
题意：环形公路 n 站，每站有油量 p_i 与到下一站距离 d_i；判断以每站为起点，
     顺（或逆）时针走完一圈且途中不缺油是否可行，输出 TAK/NIE。
思路：顺/逆时针分别处理。净油量 c_i=p_i-d_i（顺时针）或 p_i-d_{i-1}（逆时针），
     复制成 2n 求前缀和；起点 s 可行当且仅当其后的 n 项前缀和均不小于起点前缀和，
     即起点前缀和 ≤ 窗口[n]内最小前缀和（窗口起点为 s+1），用单调队列求滑动窗口最小值。
复杂度：时间 O(N)，空间 O(N)。
易错点：答案取两种方向之或；逆时针下标映射 pos=(n-s)%n；p,d 与 n 乘积超 int，用 long long。
*/
#include <bits/stdc++.h>
using namespace std;
// 对前缀和 pre，返回 res[b]=min(pre[b..b+n-1])（窗口长 n）
vector<long long> winMin(const vector<long long>& pre,int n){
    int m=(int)pre.size();
    vector<long long> res(m,LLONG_MAX);
    deque<int> q;
    for(int i=0;i<m;i++){
        while(!q.empty()&&q.front()<=i-n){
            q.pop_front();
        }
        while(!q.empty()&&pre[q.back()]>=pre[i]){
            q.pop_back();
        }
        q.push_back(i);
        if(i>=n-1){
            res[i-(n-1)]=pre[q.front()];
        }
    }
    return res;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<long long> p(n),d(n);
    for(int i=0;i<n;i++){
        cin>>p[i]>>d[i];
    }
    // 顺时针：站点顺序 0,1,...,n-1；净 = p_i - d_i
    vector<long long> cw(2*n);
    for(int k=0;k<2*n;k++){
        int st=k%n;
        cw[k]=p[st]-d[st];
    }
    vector<long long> preCw(2*n+1,0);
    for(int i=0;i<2*n;i++){
        preCw[i+1]=preCw[i]+cw[i];
    }
    vector<long long> wmCw=winMin(preCw,n);
    // 逆时针：站点顺序 0,n-1,n-2,...,1；净 = p_st - d_{(st-1+n)%n}
    vector<long long> ccw(2*n);
    for(int k=0;k<2*n;k++){
        int st=(n-(k%n))%n;
        int prev=(st-1+n)%n;
        ccw[k]=p[st]-d[prev];
    }
    vector<long long> preCcw(2*n+1,0);
    for(int i=0;i<2*n;i++){
        preCcw[i+1]=preCcw[i]+ccw[i];
    }
    vector<long long> wmCcw=winMin(preCcw,n);
    for(int s=0;s<n;s++){
        bool okCw=(preCw[s]<=wmCw[s+1]);
        int pos=(n-s)%n;
        bool okCcw=(preCcw[pos]<=wmCcw[pos+1]);
        cout<<((okCw||okCcw)?"TAK":"NIE")<<'\n';
    }
    return 0;
}
旅行问题

正文

一本通·提高篇的其它内容
