• 微信公众号：美女很有趣。 工作之余，放松一下，关注即送10G+美女照片！

# 【单调队列优化】旅行问题

6天前 5次浏览

## 代码

``````#include <deque>
#include <cstdio>
#define int long long

std::deque<int> q;
int n;
int b[2000001], a[2000001], ans[2000001];

signed main() {
scanf("%lld", &n);
for (int i = 1, x, y; i <= n; i++) {
scanf("%lld %lld", &x, &y);
a[i + n] = a[i] = x - y;
int d = n - i == 0 ? n : n - i;
b[d + n] = b[d] -= y;
b[2 * n - i + 1] = b[n - i + 1] += x;
}
for (int i = 2; i <= n * 2; i++)
a[i] += a[i - 1], b[i] += b[i - 1];
for (int i = 1; i < n * 2; i++) {
while (q.size() && i - q.front() + 1 > n)
q.pop_front();
while (q.size() && a[i] <= a[q.back()])
q.pop_back();
q.push_back(i);
if (i >= n) {
if (a[q.front()] - a[i - n] >= 0)
ans[i - n + 1] = 1;
}
}
q.clear();
for (int i = 1; i < n * 2; i++) {
while (q.size() && i - q.front() + 1 > n)
q.pop_front();
while (q.size() && b[i] <= b[q.back()])
q.pop_back();
q.push_back(i);
if (i >= n) {
if (b[q.front()] - b[i - n] >= 0)
ans[2 * n - i] = 1;
}
}
for (int i = 1; i <= n; i++)
if (ans[i])
printf("TAKn");
else
printf("NIEn");
}
``````