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