前言

传送门

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;
        }
    }
}