python/TangDou/AcWing/MonotonicQueue/1088_BruteForce.cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2000010;
int n;
int p[N];
int d[N];
LL s[N];
bool ans[N];

int main() {
    scanf("%d", &n);

    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &p[i], &d[i]);
        // 破环成链
        p[i + n] = p[i];
        d[i + n] = d[i];
    }

    // 顺时针，油量增减量的前缀和
    for (int i = 1; i <= 2 * n; i++) s[i] = s[i - 1] + p[i - 1] - d[i - 1];
    for (int i = 1; i <= n; i++) { // 枚举出发点
        LL Min = LLONG_MAX;
        // 找出每个加油站站点到达时的油量最小值，如果最小值都
        for (int j = i + 1; j <= i + n; j++) Min = min(Min, s[j]);
        if (Min >= s[i]) ans[i] = true;
    }

    // 逆时针，油量增减量的后缀和
    // 一正一反跑两回，才能说某个点是不是顺时针、逆时针可以到达全程，跑环成功
    // KAO,前缀和和后缀和一起用，居然不用重新初始化！牛！这个边界s[i+1]=0用的好啊！
    // memset(s, 0, sizeof s);
    for (int i = 2 * n; i; i--) s[i] = s[i + 1] + p[i + 1] - d[i];
    for (int i = n + 1; i <= 2 * n; i++) {
        LL Min = LLONG_MAX;
        for (int j = i - 1; j >= i - n; j--) Min = min(Min, s[j]);
        if (Min >= s[i]) ans[i - n] = true;
    }

    // 枚举输出
    for (int i = 1; i <= n; i++) puts(ans[i] ? "TAK" : "NIE");
    return 0;
}