题解 CF1304C 【Air Conditioner】

ShineEternal

2020-02-16 08:59:28

Solution

[可能更佳的阅读效果](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; } ```