题解 CF1304C 【Air Conditioner】

2020-02-16 20:21:35


其他题解怎么全是 $O(n)$的,明明 $n$ 只有 $100$ 。

这里提供一个 $O(n^2)$ 的做法。

初始温度为 $m$ ,先想象有第 $0$ 名客人, $l_0=h_0=m$ ,若对于所有 $i,j∈[0,n]$ 且 $i<j$ ,忽视其他客人的要求,可以使第 $i$ 名客人和第 $j$ 名客人满意,则答案为 $YES$ ,否则答案为 $NO$ 。

大概就是这样:

bool flag=1;
scanf("%d%d",&n,&m);
t[0]=0,l[0]=h[0]=m;
for(int i=1;i<=n;i++)
    scanf("%d%d%d",&t[i],&l[i],&h[i]);
for(int i=0;i<n;i++)
    for(int j=i+1;j<=n;j++)
        if(!work(i,j))flag=0;//work(i,j)表示忽略其他客人的情况下能否使第i名和第j名客人满意
if(flag)puts("YES");
else puts("NO");

正确性证明:

为了便于说明,先以如下图情况为例,其他情况同理:

若 $work(0,1)=1$ ,则显然可以使第 $1$ 名客人满意,且在 $y$ 轴右侧有点 $(t_1,k_1)(l_1\le k_1\le h_1)$ 在直线 $y=x+m$ 之下且在直线 $y=-x+m$ 之上 $($ 或在两直线上 $)$ 。

若 $work(1,2)=1$ ,则在直线 $x=t_1$ 右侧有点 $(t_2,k_2)(l_2\le k_2\le h_2)$ 在直线 $y=x-t_1+h_1$ 之下且在直线 $y=-x+t_1+l_1$ 之上 $($ 或在两直线上 $)$ ,也就是在上图的蓝色或绿色区域内。

若 $work(0,2)=1$ ,则在 $y$ 轴右侧有点 $(t_2,k_{2'})(l_2\le k_{2'}\le h_2)$ 在直线 $y=x+m$ 之下且在直线 $y=-x+m$ 之上 $($ 或在两直线上 $)$ ,也就是在上图的橙色或绿色区域内。

若 $work(0,1)=work(0,2)=work(1,2)=1$ ,则有点 $(t_2,k_{2''})(l_2\le k_{2''}\le h_2)$ 在上图的绿色区域内,然后就显然可以同时使第 $1、2$ 位客人满意。

然后以此类推即可。

完整代码:

#include<bits/stdc++.h>
using namespace std;
#define N 105
int q,n,m,t[N],l[N],h[N];
bool work(int i,int j){
    if(l[i]>=l[j]&&l[i]<=h[j])return 1;
    if(h[i]>=l[j]&&h[i]<=h[j])return 1;
    if(l[j]>=l[i]&&l[j]<=h[i])return 1;
    if(h[j]>=l[i]&&h[j]<=h[i])return 1;
    if(l[i]>h[j]&&l[i]-h[j]>t[j]-t[i])return 0;
    if(h[i]<l[j]&&l[j]-h[i]>t[j]-t[i])return 0;
    return 1;
}
int main(){
    scanf("%d",&q);
    while(q--){
        bool flag=1;
        scanf("%d%d",&n,&m);
        t[0]=0,l[0]=h[0]=m;
        for(int i=1;i<=n;i++)
            scanf("%d%d%d",&t[i],&l[i],&h[i]);
        for(int i=0;i<n;i++)
            for(int j=i+1;j<=n;j++)
                if(!work(i,j))flag=0;
        if(flag)puts("YES");
        else puts("NO");
    }
    return 0;
}