原题：https://fjnuacm.top/d/junior/p/P1304C

空调凉凉~

题意

一个餐馆中有个空调，给定空调的初始温度为 \(m\)，每分钟可以选择上调或下调 \(1\) 个单位的温度，或选择不变。

给定 \(n\) 个食客的到达时间 \(t_i\) 以及所能适应的温度范围 \([l_i, r_i]\)，每个食客只会在 \(t_i\) 时刻逗留。

如果温度不在食客的适应范围内，他就会不舒服。输出空调能否使得所有食客都感到舒服。

思路

当初第一反应是维护一个温度值，根据食客的需求改变温度。但这里存在问题：对于有限的操作，最后能落在温度区间的温度是不唯一的。如果是这样，很多种可能叠加，不难发现会超时。

也许我们可以贪心地认为只要满足最低条件即可，但我们不能保证下一个本因可行的区间可能被判为不可行（如一直递增的温度区间）。

单个值失败了，那就多个值呗。

我们只要维护一个区间，让每次所有的可行解落在该区间。然后，对于每一个区间，将其与后面的区间进行区间重叠运算。

对于重叠的区间，有四种可能：

1.可行区间 \(cur\) 和后一个温度区间没有重叠

2.两区间左侧或右侧部分重叠

3.可行区间 \(cur\) 包含于后一个温度区间

4.可行区间 \(cur\) 被包含于后一个温度区间

对应AC代码

import java.util.*;

public class Main {

    static class Person{
        long t, l, h;
        Person(long t, long l, long h){
            this.t = t;
            this.l = l;
            this.h = h;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int q = scanner.nextInt();
        g:for(int i=0;i<q;i++){
            int n = scanner.nextInt(), m = scanner.nextInt();
            Person[] p = new Person[n];
            for(int j=0;j<n;j++) p[j] = new Person(scanner.nextLong(), scanner.nextLong(), scanner.nextLong());
            long left = m - p[0].t, right = m + p[0].t; //以第一个人的到达时间划分初始区间
            for(int j=0;j<n;j++){
                Person cur = p[j];
                if(cur.h < left || cur.l > right){
                    System.out.println("NO");
                    continue g;
                }else if(j == n - 1){ //如果是最后一个，只要有交集就已经成功
                    System.out.println("YES");
                    continue g;
                }
                if(cur.l >= left && cur.h <= right){ //包含关系
                    left = cur.l;
                    right = cur.h;
                }else if(cur.l >= left) left = cur.l; //右侧有区间重叠
                else if(cur.h <= right) right = cur.h; //左侧有区间重叠
                left -= p[j + 1].t - cur.t;
                right += p[j + 1].t - cur.t;
            }
        }
    }
}

第一次写题解，可能交代的不是很清楚。