蓝桥3898.泡澡 ​

题目 ​

1.泡澡 - 蓝桥云课

问题描述 ​

在一个寒冷的冬天，有 $N$ 个人想要去澡堂泡澡，第 $i$ 个人会在时间段 $[S_i,T_i)$（不包括 $T_i$）内每分钟使用 $P_i$ 升热水。由于该澡堂设备简陋，无法存储热水。热水器在每分钟最多能提供 $W$ 升热水。现在请问该澡堂能否满足这 $N$ 个人的泡澡需求，如果可以请输出 $Yes$，否则输出 $No$。

输入格式 ​

第一行包含两个整数 $N$ 和 $W$，表示洗澡的人数和热水器的容量。

接下来 $N$ 行，每行包含三个整数 $S_i$，$T_i$ 和 $P_i$（$0\le S_i<T_i\le 2\times {10}^5$，$1\le W,P_i\le {10}^9$），表示第 $i$ 个人的洗澡计划。其中 $S_i$ 和 $T_i$ 表示计划的开始时间和结束时间，$P_i$ 表示每分钟需要的热水量。

输出格式 ​

如果可以按照所有人的计划供应热水，则输出 $Yes$，否则输出 $No$。

样例输入 ​

2 5
1 3 3
2 3 3

样例输出 ​

No

样例说明 ​

在时间段 $[2,3)$ 分钟内，第 $1$ 个人需要 $3$ 升热水，第 $2$ 个人也需要 $3$ 升热水，总共需要 $6$ 升热水，此时热水器无法满足。

题解 ​

首先，因为$0\le S_i<T_i\le 2\times {10}^5$，区间长度是比较大的，遍历有可能导致超时。可以看出，每一组S, T, P都是在一个区间范围内统一加一个数，让人联想到差分数组。

构建一个差分数组，由于初始时，所有时刻用水量均为0：（1）用水量为0 --> diff[1]=0（下标从1开始）；（2）所有时刻都为0 --> diff[i]=0

根据输入的S, T, P，可以对差分数组在区间两端的数字进行增减。具体来说，如果我们想在区间 [s, t) 内每个元素加上 p，我们只需要执行以下操作：

• diff[s] += p
• diff[t] -= p 由于差分数组的下标通常是从 1 开始，假设时间是从 0 开始的，区间 [s, t) 表示从时间 s 到时间 t-1。为了在差分数组中正确表示这个区间，我们需要将 s 和 t 都加 1。这样，diff[s+1] += p 表示在时间 s 开始加上 p，而 diff[t+1] -= p 表示在时间 t 结束时减去 p。

值得注意的是，在所有人的洗澡需求输入之前，我们并不知道最大的时间区间是多少，因此为了避免麻烦，在一开始便开一个较大的列表来存储差分数组，其中要考虑到0不取，最大时间+1的这个范围。

最后的最后，将差分数组作前缀和，便可以得到“原数组”，即每个时间段的用水量统计，判断最大用水量是否在规定范围内即可。

TIME=200000
n,w=map(int,input().split())
diff=[0]*(TIME+2) #包括了0和TIME+1
tm=0 #最晚时间
for _ in range(n):
	 s,t,p=map(int,input().split())
	 diff[s+1]+=p 
	 diff[t+1]-=p  
	 tm=max(t,tm)
res=[0]*(tm+1)
for i in range(1,tm+1):
	 res[i]=res[i-1]+diff[i]
if max(res)>w:
	print('No')
else:
	print('Yes')