思路:看到数据范围,首先想到这个算法上界是 O(TNlogV)
考虑最简单的情况:n=2 时,两者时间差为t
让顾客2满足要求,则需要顾客1的当前温度M_1加上 t 或减去 t 在[L_2,R_2]范围内
那么很显然,我们并不需要考虑M_1具体是多少,只要求出它的左右边界即可
对于顾客3,也是可以这样考虑顾客2,依次类推,设计出一个算法:
设定边界 L,R 是当前第 i 个人可以调节到的温度,则 [L-t,R+t] 是第 i+1 个人能调节到的温度
判断一下其与 [L_i+1,R_i+1] 的交集是否为空集即可。
然后再一次取得 L,R 的范围
代码如下:
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 const int maxn = 105; 6 int n,m; 7 struct cust { 8 int l,r,t; 9 cust() { 10 l = r = t = 0; 11 } 12 bool operator < (const cust& p)const { 13 return t < p.t; 14 } 15 }a[maxn]; 16 void work() { 17 scanf("%d%d",&n,&m); 18 for(int i = 1;i <= n;++ i)scanf("%d%d%d",&a[i].t,&a[i].l,&a[i].r); 19 sort(a + 1 , a + 1 + n); 20 int L = m,R = m; 21 for(int i = 1;i <= n;++ i) { 22 int val = a[i].t - a[i - 1].t; 23 L -= val; 24 R += val; 25 if(L > a[i].r||R < a[i].l) { 26 puts("NO"); 27 return ; 28 } 29 L = max(L , a[i].l); 30 R = min(R , a[i].r); 31 } 32 puts("YES"); 33 return ; 34 } 35 int main() { 36 int T; 37 scanf("%d",&T); 38 while(T --)work(); 39 return 0; 40 }View Code