P3422 [POI2005] LOT-A Journey to Mars

_BACKFIRE_ · 2023-07-12 15:14:22 · 题解

前言

传送门

blog

长沙市一中暑假第一次思维训练。

前置芝士

前缀和

单调队列

思路

在考试过程中突然发现与好消息，坏消息题目大致相同，不同之处只有这个可以往逆时针方向走，以此确定本题算法——前缀和与单调队列。

首先我们可以算出每一个站点可以拿到的油 p_i - d_i，也就是油量 - 到下一站的距离，然后我们就将其围成一个环，如下图。

这样在我们随意选取以 x 开头的长度为 n 的一段，这时候也就算我们走完一圈 。而我们所要知道的就是在这一段之中，有没有油量 \le 0 的时候，我们可以使用前缀和算取某一段区间的油量的总合。

我们要把每一段都算一遍吗？不对，只需要用最小的减去当前的，如果最小的不行，那此方案肯定是不行的。

如何维护最小值呢？我们可以使用单调队列维护，接下来就可以写代码了。

AC Code

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

int n,p[2000010],d[2000010],sum[2000010];

bool ans[2000010];

signed main(){
    scanf("%lld",&n);
    for(int i = 1;i <= n;i++)
        scanf("%lld%lld",p + i,d + i);
    for(int i = 1;i < n;i++){
        sum[i + n] = sum[i] = p[i] - d[i];
    }
    for(int i = 1;i < 2 * n;i++){
        sum[i] += sum[i - 1];
    }
    deque<int>q;
    for(int i = 2 * n - 1;i;i--){
        while(!q.empty() && q.front() >= i + n)q.pop_front();
        while(!q.empty() && sum[q.back()] >= sum[i]) q.pop_back();
        q.push_back(i);
        if(i <= n){
            if(sum[q.front()] >= sum[i - 1]){
                ans[i] = 1;
            }
        }
    }

    d[0] = d[n];
    for(int i = 1;i < n;i++){
        sum[i + n] = sum[i] = p[i] - d[i - 1];
    }
    for(int i = 1;i < 2 * n;i++){
        sum[i] += sum[i - 1];
    }
    deque<int>x;
    for(int i = 1;i < n * 2;i++){
        while(!x.empty() && x.front() < i - n)x.pop_front();
        if(i > n){
            if(sum[x.front()] <= sum[i]){
                ans[i - n] = 1;
            }
        }
        while(!x.empty() && sum[x.back()] <= sum[i]) x.pop_back();
        x.push_back(i);
    }
    for(int i = 1;i <= n;i++){
        if(ans[i]){
            cout<<"TAK"<<endl;
        }else{
            cout<<"NIE"<<endl;
        }
    }
}