0%

FjnuOJ - 模拟 - Air Conditioner

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

空调凉凉~

题意

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

给定 个食客的到达时间 以及所能适应的温度范围 ,每个食客只会在 时刻逗留。

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

思路

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

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

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

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

对于重叠的区间,有四种可能:

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

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

3.可行区间 包含于后一个温度区间

4.可行区间 被包含于后一个温度区间

对应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;
            }
        }
    }
}

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