题目描述

难度分:$1500$

输入$T(\leq 500)$表示$T$组数据。每组数据首先输入$n(1 \leq n \leq 100)$，$t_0(-10^9 \leq t0 \leq 10^9)$。

老兵烤肉今天要迎接$n$位顾客，在第$0$分钟，空调温度为$t_0$。

然后输入$n$行，第$i$行输入$t(1 \leq t \leq 10^9)$，$low$，$high(-10^9 \leq low \leq high \leq 10^9)$，表示第$i$名顾客会在第$t$分钟到达，这名顾客偏好的温度范围是闭区间$[low,high]$。

保证$t$非递减，即第$i$名顾客的$t \leq$第$i+1$名顾客的$t$。

空调温度每分钟可以$+1$，$-1$或不变。能否让所有顾客（仅在到店时刻）都对温度满意？输出YES或NO。

输入样例

4
3 0
5 1 2
7 3 5
10 -1 0
2 12
5 7 10
10 16 20
3 -100
100 0 0
100 -50 50
200 100 100
1 100
99 -100 0

输出样例

YES
NO
YES
NO

算法

贪心

要转弯的一个题目，$n$的范围具有迷惑性。从$t[1]$时刻开始考虑，上一个时刻$0$的温度是$t_0$，那么从上一个时刻到现在一共经历了$deltaT=t[1]-0$秒，这$deltaT$秒可以下调温度，上调温度或不变，因此$[t_0-deltaT,t_0+deltaT]$的温度都是有可能达到的，只要这个区间的温度和$[low[1],high[1]]$有交集，那第$1$位顾客就可以满足，让第$1$位顾客到达时室温在这个交集区间内即可，具体是多少不重要。

接下来考虑后面的顾客，每次都和第$1$位顾客类似。根据上一位顾客的温度区间以及当前顾客的到达时间与上一位顾客到达时间的差值，算出到当前顾客到达时间点的温度区间，看和区间$[low[i],high[i]]$是否有交集。没有交集就停止遍历，输出NO表示有顾客不能满足；否则就在遍历完所有顾客的到达时间后输出YES，表示所有顾客都能满足。

复杂度分析

时间复杂度

遍历一遍$i \in [1,n]$就能判断，因此时间复杂度为$O(n)$。

空间复杂度

除了输入的$t$、$low$、$high$数组，仅使用了有限几个变量，额外空间复杂度为$O(1)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 110;
int T, n, t0, t[N], low[N], high[N];

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &n, &t0);
        t[0] = 0;
        for(int i = 1; i <= n; i++) {
            scanf("%d%d%d", &t[i], &low[i], &high[i]);
        }
        bool flag = true;
        int left = t0, right = t0;
        for(int i = 1; i <= n; i++) {
            int deltaT = t[i] - t[i - 1];
            left = max(low[i], left - deltaT), right = min(high[i], right + deltaT);
            if(left > right || right < low[i] || left > high[i]) {
                flag = false;
                break;
            }
        }
        if(flag) {
            puts("YES");
        }else {
            puts("NO");
        }
    }
    return 0;
}