题解 CF1304C 【Air Conditioner】
ShineEternal
2020-02-16 08:59:28
[可能更佳的阅读效果](https://blog.csdn.net/kkkksc03/article/details/104338252)。
## description:
- 一个餐馆中有个空调,每分钟可以选择上调 $1$ 个单位的温度或下调 $1$ 个单位的温度,当然你也可以选择不变,初始的温度为 $m$ 。
- 有 $n$ 个食客,每个食客会在 $t_i$ 时间点到达,他所能适应的最低温度是 $l_i$ ,最高温度是 $h_i$ ,他只会在 $t_i$ 时刻逗留。
- 如果温度不在食客的适应范围内,他就会不舒服,请你判断,空调能否使得 $n$ 位来就餐的食客都感到舒服。
- **本题多组数据**,数据组数不大于 $500$。
- $1\le n\le 100$,$-10^9\le m,l_i,h_i\le 10^9$,$1\le t_i\le 10^9$。
- translate by @[ShineEternal](https://www.luogu.com.cn/user/45475)。
## solution:
设刚开始的区间为 $[tmpl,tmpr]$。
其中 $tmpl=tmpr=m$。
那么每次我们能调节到的温度区间为 $[tmpl-\Delta t,tmpr+\Delta t]$。
其中 $\Delta t=t_i-t_{i-1}$。
这是因为我们再规定时间内能将温度调节到这个区间内的任意一点。
然而具体怎样调我们并不关心。
然后这一次我们判断 $[tmpl-\Delta t,tmpr+\Delta t]$ 与 $[l_i,h_i]$ 有无交集即可。
如果不在区间里直接一次就 `no` 了,在区间里因为我们必须要等到那个时间点游客打完酱油再调温度,所以要将温度卡到对应的舒适区间。(这里第二组样例是一个很好的解释。)
## code:
```cpp
#include<cstdio>
#include<algorithm>
using namespace std;
long long t[105],l[105],h[105];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n;
long long m;
long long tmpT=0;
scanf("%d%lld",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%lld%lld%lld",&t[i],&l[i],&h[i]);
}
long long L=m,r=m;
int flag=0;
for(int i=1;i<=n;i++)
{
L=L-(t[i]-t[i-1]);
r=r+(t[i]-t[i-1]);
if(L>h[i]||r<l[i])
{
printf("NO\n");
flag=1;
break;
}
else
{
L=max(L,l[i]);
r=min(r,h[i]);
}
}
if(flag==0)
{
printf("YES\n");
}
}
return 0;
}
```