【AcWing】蓝桥杯集训每日一题Day1|二分|差分|503.借教室(C++)

503. 借教室

---

题目内容

在大学期间，经常需要租借教室。
大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。
教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。 
面对海量租借教室的信息，我们自然希望编程解决这个问题。
我们需要处理接下来$n$天的借教室信息，其中第$i$天学校有$r_i$个教室可供租借。
共有$m$份订单，每份订单用三个正整数描述，分别为$d_j,s_j,t_j$表示某租借者需要从第$s_j$天到第$t_s$天租借教室（包括第$s_j$天和第$t_j$天），每天需要租借$d_j$个教室。 
我们假定，租借者对教室的大小、地点没有要求。
即对于每份订单，我们只需要每天提供$d_j$个教室，而它们具体是哪些教室，每天是否是相同的教室则不用考虑。
借教室的原则是先到先得，也就是说我们要按照订单的先后顺序依次为每份订单分配教室。
如果在分配的过程中遇到一份订单无法完全满足，则需要停止教室的分配，通知当前申请人修改订单。
这里的无法满足指从第$s_j$天到第$t_j$天中有至少一天剩余的教室数量不足$d_j$个。 
现在我们需要知道，是否会有订单无法完全满足。
如果有，需要通知哪一个申请人修改订单。

输入格式

第一行包含两个正整数 $n,m$，表示天数和订单的数量。 
第二行包含$n$个正整数，其中第$i$个数为$r_i$，表示第$i$天可用于租借的教室数量。 
接下来有$m$行，每行包含三个正整数 $d_j,s_j,t_j$，表示租借的数量，租借开始、结束分别在第几天。 
每行相邻的两个数之间均用一个空格隔开。
天数与订单均用从 11 开始的整数编号。

输出格式

如果所有订单均可满足，则输出只有一行，包含一个整数0。
否则（订单无法完全满足）输出两行，第一行输出一个负整数 −1，第二行输出需要修改订单的申请人编号。

数据范围

$1\le n,m\le 10^6$
$0\le r_i,d_j\le 10^9$
$1\le s_j\le t_j\le n$

输入样例：

4 3
2 5 4 3
2 1 3
3 2 4
4 2 4
1
2
3
4
5

输出样例：

-1
2
1
2

题目解析

数据范围在$10^6$，时间复杂度要控制在$O(n\log n)$/$O(n)$
如何通过数据范围判断时间复杂度可以参考这篇文章
蓝桥杯暴力求解与高频考点-CSDN博客
如果直接模拟，不优化的话

可以从前往后依次遍历每个订单，可以开个数组，统计一下每一天一共需要多少教室
从$s\dots t$天，每天需要$d$个教室，可以枚举for循环一下，从s~t枚举一遍，cnt[i]+=d，每次加完之后，判断这一天需要教室数量是不是小于给定教室数量，如果是的话，表示满足；不是的话，表示不满足。
一共需要处理$10^6$个订单，每个订单的区间长度最大$O(n)=10^6$，时间复杂度就是$10^6\ast 10^6=10^{12}$，肯定会TLE(Time Limit Exceeded时间超限)。
如果代码不想超时，需要将时间复杂度控制在$10^8$以内(1s是$10^8$)

优化的话
如果按照题意进行动态地做，动态地给每一个区间加上同一个d，然后再去动态地判断这个区间内的某一个值是不是大于给定的值。

可以用线段树来做，可是线段树时间复杂度比较高，可能会TLE，线段树的题目n一般会给到$10^5$。要使用比线段树常数更小的算法

1. 差分

如果把这个题变成一个判定性的问题，
判断一下能不能处理前k个订单，这个时候，这个题目就变成了给k个区间，每个区间加一个相同的数，加完之后需要计算一下每个数最终的值是多少

经典的模板题，相当于算法里的公式
797.差分
有一个标准做法，可以做到线性的时间复杂度$O(n+m)$。
判定性问题可以用差分来做

差分的原理

比如每一天可以用的教室数量是$r_1\dots r_n$，用数组r表示
要统计一下每天需要多少教室$a_1\dots a_n$，用a数组来表示
初始的时候都是0，
给一个s~t的订单，给$a_s\dots a_t$之间的每个数全部加上一个d
先将a数组进行一个变形
让$a_0=0$，
$b_1=a_1-a_0$，$b_2=a_2-a_1$以此类推，一直到$b_n=a_n-a_{n-1}$
相当于对a数组进行一个差分变换
发现
如果给我们一个差分数组b，可以把原数组a反推回来
给原数组a，可以把差分数组b求出来
差分数组和原数组的信息量是一模一样的
差分数组推原数组
$a_1=b_1+a_0=b_1$
$a_2=b_2+a_1=b_1+b_2$
$a_n=b_n+a_{n-1}=b_1+\cdots +b_n$
原数组就是差分数组的前缀和数组

转换完之后
如果想对s~t，每个数加上一个d的话
如果要对原数组操作，要去修改$O(n)$个数
但是这个操作对差分数组的影响就很少了
$$\begin{array}{c}{b}_1=a_1-a_2\\ b_2=a_2-a_1\\ \dots \\ b_{s-1}=a_{s-1}-a_{s-2}\\ b_s=a_s-a_{s-1}\\ b_{s+1}=a_{s+1}-a_s\\ \dots \\ b_t=a_t-a_{t-1}\\ b_{t+1}=a_{t+1}-a_t\\ b_{t+2}=a_{t+2}-a_{t+1}\\ \dots \end{array}$$
这个操作只会对$a_s\dots a_t$将每个数全部加上d
因此
$b_1\dots b_{s-1}$都是不变的，因为$a_0\dots a_{s-1}$不变，所以差值也不变
$b_s$的话，$a_s$加上一个d，$a_{s-1}$不变，所以$b_s$加了一个d
$b_{s+1}\dots b_t$，由于$a_s\dots a_t$每个数全部加了一个d，所以差值是不变的，所以b都是不变的
$b_{t+1}$的话，$a_{t+1}$不变，$a_t$加了一个d，所以差值会减一个d，所以$b_{t+1}$减一个d
$b_{t+2}$开始到后面的，因为从$a_{t+1}\dots a_n$一直都不变，所以不变
$$\begin{array}{c}\\ 不变\{\begin{array}{l}{b}_1=a_1-a_2\\ b_2=a_2-a_1\\ \dots \\ b_{s-1}=a_{s-1}-a_{s-2}\end{array}\\ +d{b}_s=a_s-a_{s-1}\\ 不变\{\begin{array}{l}{b}_{s+1}=a_{s+1}-a_s\\ \dots \\ b_t=a_t-a_{t-1}\end{array}\\ -d{b}_{t+1}=a_{t+1}-a_t\\ 不变\{\begin{array}{l}{b}_{t+2}=a_{t+2}-a_{t+1}\\ \dots \end{array}\end{array}$$

对于原数组的操作，本来要操作$O(n)$个数，对于差分数组的影响，只会影响$b_s$和$b_{t+1}$两个数，这样就可以将修改操作从$O(n)$变成$O(1)$
改变$O(n)$个数，需要两层循环，现在只用改变两个数，就不用写循环了，可以把时间复杂度从$O(n^2)$变成$O(n)$
这样的话每个操作就不要对原数组操作，而是对差分数组进行操作，差分数组求完之后，再通过差分数组求出来原数组，相当于做一个变换

这样可以用$O(n+m)$的时间复杂度，判断出前k个订单有没有出现矛盾

2. 二分

原问题
把所有的订单取出来，编号是1~m
先到先得，按照编号顺序依次处理每个订单

二段性

这些个能处理的订单，有一个二段性
比如说在这个问题里面，第k个订单是最后一个能处理的订单
从第k+1个订单开始就不能处理了

把前k个区间全部加到数组上，每一天需要的教室数量都是小于等于给定的教室数量，对于k前面的任何一个数x，同样能处理x个订单，显然是成立的
前x个订单严格比前k个订单少一些区间，相当于在某些数上少加了一些d，加上那些之后不会超过给定值，不加那些数同样不会超过给定值
最后一个能处理的订单是第k个订单的话，对于小于等于k等任何一个数x，前x个订单一定都是可以处理的

同理

第一个不能处理的订单是第k+1个订单的话，如果把前k+1个区间加到天数数组r上的话，一定会有某一天，它需要的教室数量大于给定值
对于大于等于k+1的任何一个x，1~x一定也都是不能处理的

因为前k+1个区间加完之后，在某一天已经大于给定值了，再加上一些额外的数，仍然会大于给定值

---

对于x来说，当x取1~k之间的数的时候，它是满足的
当x大于k的时候，是不满足的

具有二段性的话，就可以通过二分把这个边界二分出来，
789.数的范围

如何二分

比如最后一个能处理的订单是第k个订单，
左右边界是1~m
每次二分一个中点mid
如果1~mid，能满足的话，说明最后一个能满足的订单在mid或者在mid的右边，所以答案会落在$[mid,m]$这个区间，

就可以删掉左边的区间，把二分的左端点L设成mid

再二分中点
取一个mid，如果处理mid这个订单会出现矛盾，说明1~mid是无法处理的，说明最后一个能处理的订单在mid的严格左边

因此相当于把右边的区间删掉，把右端点R置成mid-1

每次将搜索范围缩小一半，缩小完之后保证答案一定在搜索范围内，最后当范围内只有一个数的时候，它就是答案

二分模板用哪个，取决于mid属于左半边区间还是右半边区间，取整的问题，二分的话，整数不一定能够刚好整除，奇数的话是上取整还是下取整，如果模板用错可能会有死循环

代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;
//算前缀和，10^6个10^9，有可能会爆int，需要用到long long

const int N = 1000010;

int n, m;
int w[N];
//用w存r，不用r，因为二分的时候会用到变量r，防止变量冲突
int d[N], s[N], t[N];
LL b[N];

//检查前mid订单能不能满足
bool check (int mid)
{
	memset(b, 0, sizeof b); //先把差分数组初始化为0，不能让上次检查的结果，影响下次检查的过程
	for (int i = 1; i <= mid; i++) //依次处理每一个订单
	{
		b[s[i]] += d[i];
		b[t[i] + 1] -= d[i];
	}

	LL s = 0;  //用一个前缀和来计算当前的每一a_i是多少
	for (int i = 1; i <= n; i++) //以此类推每一天
	{
		s += b[i]; //每次更新一下前缀和
		if (s > w[i]) return false;  //发现当前教室数量大于给定教室数量,return false
	}

	return true;  //否则return true
}

int main()
{
	scanf("%d%d", &n, &m);
	for (int 1 = 1; i <= n; i++) scanf("%d", &w[i]);
	//依次读入每天可以用的教室数量
	for (int i = 1; i <= m; i++) scanf("%d%d%d", &d[i], &s[i], &t[i]);
	//依次读入m个订单d，s，t，订单数量和起始时间

	//二分
	int l = 0; r = m;   //0表示一个订单都不能满足
	while (l < r)
	{
		//求中点
		int mid = l + r + 1 >> 1; //因为l=mid，+1用上取整；如果r=mid，用下取整
		if (check(mid)) l = mid;  //如果发现[1,mid)可以满足，表示答案应该在[mid,m]
		else r = mid -1;
	}

	if (r == m) puts("0"); //如果发现所有订单都能满足，输出0
	else printf("-1\n%d\n", r + 1); //否则第一行输出-1，第二行输出第一个不能满足的订单编号

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60