题面
大秦为你打开题目传送门
题目描述
给你一个环形跑道，一开始你只能走 $0$ 公里（如果你选择了从第 $i$ 个节点开始的话，那就是 $p_i$ 公里），第 $i$ 个节点可以让你多走 $p_i$ 公里，第 $i$ 个节点距离下一个节点有 $d_i$ 公里。对于每一个节点，如果能从他出发顺时针或逆时针走遍所有空间站，输出 TAK 否则输出 NIE 。
思路
那么遇到这种环上的问题，第一步就是破环为链。这样的话可以免去这个跳一圈算来算去的事情。
然后再看看题目，如果起始点一样的话顺时针和逆时针其实就是反过来算的关系，所以说我们就考虑一个方向，然后到时候反过来做一遍就可以了。那么方便起见先考虑顺时针。
那么根据上面我稍微缩减了的题面，从某一个节点加完油出来，到达下一个节点的这个过程，其实就是 $p_i - d_i$ 这样的过程。正的 $p_i$ 是加的油量，负的 $d_i$ 表示走这么一段路我们会花掉那么多的油量。
也就是说，这个点的贡献我们可以认为就是 $p_i - d_i$ 。那么我们一开始的油量是 $0$ 这样一个一个经过节点的过程，其实就是求前缀和的过程，如果某一刻前缀和小于等于 $0$ 那么就说明车用不了了。
那么如果暴力的去找到这个对于枚举出来的起点 $i$ 变为负数的前缀和 $sum_j$ 复杂度就是 $O(n^2)$ 的。不可以过掉此题。
那其实就是优化这样的过程了。
我们观察这个式子 $sum_j - sum_i \le 0$ ，发现如果移项变成 $sum_j \le sum_i$ 其实就只和 $j$ 有关了。这时候就可以使用单调队列去维护。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
|
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 int128;
namespace FastIO
{
template<typename T> inline T read(T& x) {
x = 0;
int f = 1;
char ch;
while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
x *= f;
return x;
}
template<typename T, typename... Args> inline void read(T& x, Args &...x_) {
read(x);
read(x_...);
return;
}
inline ll read() {
ll x;
read(x);
return x;
}
};
using namespace FastIO;
const int N = 2e6 + 10;
template<typename T, unsigned int N, bool (*func)(T, T)>
class MQueue {
private :
pair<T , int >q[N];
int hd, tl, len;
public :
inline void clear(int len) { this->len = len; hd = 0, tl = -1; }
inline int size() { return tl - hd + 1; }
inline bool empty() { return hd > tl; }
inline void push(pair<T, int> ele) {
while(!empty() && (*func)(ele.first, q[tl].first)) tl--;
q[++tl] = ele;
while(!empty() && q[hd].second <= ele.second - len) hd++;
}
inline T front() { return q[hd].first; }
};
ll n;
ll p[N], d[N];
ll ans[N], flag[N];
ll sum[N], c[N];
bool cmp(ll a, ll b) { return a <= b; }
MQueue<ll, N, cmp> q;
inline void Input() {
read(n);
for(int i = 1; i <= n; i++) {
read(p[i], d[i]);
p[i + n] = p[i], d[i + n] = d[i];
c[i + n] = c[i] = p[i] - d[i];
}
}
inline void MQsolve() {
q.clear(n);
for(int i = 1; i <= n; i++) {
sum[i] = sum[i - 1] + c[i];
}
for(int i = 1; i <= n; i++) {
sum[i + n] = sum[i + n - 1] + c[i];
}
for(int i = 1; i <= n * 2; i ++) {
q.push(make_pair(sum[i], i));
if(i >= n) ans[i - n + 1] = q.front();
}
}
inline void Work() {
MQsolve();
for(int i = 1; i <= n; i++) {
if(ans[i] >= sum[i - 1]) {
flag[i] = 1;
}
}
for(int i = 1; i <= n; i++) {
c[i] = p[n - i + 1] - d[((n - i ? n - i : n))];
}
MQsolve();
for(int i = 1; i <= n; i++) {
if(ans[i] >= sum[i - 1]) {
flag[n - i + 1] = 1;
}
}
for(int i = 1; i <= n; i++) {
if(flag[i]) printf("TAK\n");
else printf("NIE\n");
}
}
int main() {
int T = 1;
while(T--) {
Input();
Work();
}
return 0;
}
|
