CF1304C Air Conditioner 题解

题目链接：Air Conditioner

题意：

一个餐馆中有个空调，每分钟可以选择上调 $1$ 个单位的温度或下调 $1$ 个单位的温度，当然你也可以选择不变，初始的温度为 $m$ 。

有 $n$ 个食客，每个食客会在 $t_i$ 时间点到达，他所能适应的最低温度是 $l_i$ ，最高温度是 $r_i$ ，他只会在 $t_i$ 时刻逗留。

如果温度不在食客的适应范围内，他就会不舒服，请你判断，空调能否使得 $n$ 位来就餐的食客都感到舒服。

本题多组数据，数据组数不大于 $500$。

$1\le n\le 100$，$-10^9\le m,l_i,r_i\le 10^9$，$1\le t_i\le 10^9$​ 。

鉴于 $l_i,r_i$ 的范围，我们不可能（也不需要）求出具体的调节方案。

设 $[l,r]$ 表示当前能达到的区间，初始 $l = r= m$ 。

每经过 $t$ 分钟，当前能到达的区间就变成了 $[l - t, r + t]$ 。

考虑第 $i$ 个顾客，经过了 $d=t_i - t_{i-1}$ 分钟，可到达区间为 $[l-d,r+d]$ 。

我们把这个区间与 $[l_i,r_i]$ 取交集，如果为空则无解，否则我们得到了满足前 $i$ 个顾客时仍能到达的区间

时间复杂度 $\mathcal{O}(n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(111))

struct node { int t, l, r; } a[N];
void solve()
{
    int n, m; cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i].t >> a[i].l >> a[i].r;
    sort(a + 1, a + 1 + n, [](node a, node b) { return a.t < b.t; });
    int l = m, r = m; bool ok = true;
    for(int i = 1; i <= n; i++)
    {
        up(l -= a[i].t - a[i - 1].t, a[i].l);
        down(r += a[i].t - a[i - 1].t, a[i].r);
        if(l > r) { ok = false; break; }
    }
    cout << (ok ? "YES" : "NO") << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int qwq; cin >> qwq; while(qwq--) solve();
    return 0;
}