NOIP2012 提高组 借教室 题解

题目描述/n/n在大学期间，经常需要租借教室。大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。/n/n面对海量租借教室的信息，我们自然希望编程解决这个问题。/n/n我们需要处理接下来 'n' 天的借教室信息，其中第 'i' 天学校有 'ri' 个教室可供租借。共有 'm' 份订单，每份订单用三个正整数描述，分别为 'dj, sj, tj'，表示某租借者需要从第 'sj' 天到第 'tj' 天租借教室（包括第 'sj' 天和第 'tj' 天），每天需要租借 'dj' 个教室。/n/n我们假定，租借者对教室的大小、地点没有要求。即对于每份订单，我们只需要每天提供 'dj' 个教室，而它们具体是哪些教室，每天是否是相同的教室则不用考虑。/n/n借教室的原则是先到先得，也就是说我们要按照订单的先后顺序依次为每份订单分配教室。如果在分配的过程中遇到一份订单无法完全满足，则需要停止教室的分配，通知当前申请人修改订单。这里的无法满足指从第 'sj' 天到第 'tj' 天中有至少一天剩余的教室数量不足 'dj' 个。/n/n现在我们需要知道，是否会有订单无法完全满足。如果有，需要通知哪一个申请人修改订单。/n/n## 输入格式/n/n第一行包含两个正整数 'n,m'，表示天数和订单的数量。/n/n第二行包含 'n' 个正整数，其中第 'i' 个数为 'ri'，表示第 'i' 天可用于租借的教室数量。/n/n接下来有 'm' 行，每行包含三个正整数 'dj, sj, tj'，表示租借的数量，租借开始、结束分别在第几天。/n/n每行相邻的两个数之间均用一个空格隔开。天数与订单均用从 '1' 开始的整数编号。/n/n## 输出格式/n/n如果所有订单均可满足，则输出只有一行，包含一个整数 '0'。否则（订单无法完全满足）/n/n输出两行，第一行输出一个负整数 '-1'，第二行输出需要修改订单的申请人编号。/n/n## 样例 #1/n/n### 样例输入 #1/n/n/n4 3 /n2 5 4 3 /n2 1 3 /n3 2 4 /n4 2 4/n/n/n### 样例输出 #1/n/n/n-1 /n2/n/n/n## 提示/n/n【输入输出样例说明】/n/n第 '1 '份订单满足后，'4 '天剩余的教室数分别为 '0,3,2,3'。第 '2' 份订单要求第 '2 '天到第 '4' 天每天提供' 3 '个教室，而第 '3' 天剩余的教室数为' 2'，因此无法满足。分配停止，通知第'2' 个申请人修改订单。/n/n【数据范围】/n/n对于10%的数据，有'1≤ n,m≤ 10'；/n/n对于30%的数据，有'1≤ n,m≤1000'；/n/n对于 70%的数据，有'1 ≤ n,m ≤ 10^5'；/n/n对于 100%的数据，有'1 ≤ n,m ≤ 10^6,0 ≤ ri,dj≤ 10^9,1 ≤ sj≤ tj≤ n'。/n/n/nNOIP 2012 提高组 第二天 第二题/n/n2022.2.20 新增一组 hack 数据/n用C++，前缀和与差分内容：## 解题思路/n/n我们需要按照订单的先后顺序依次为每份订单分配教室，并且要判断每天剩余的教室数量是否足够。/n/n首先，我们可以使用一个数组 rooms 来表示每天可用的教室数量，根据输入的 ri 初始化该数组。/n/n然后，我们遍历每份订单，对于每份订单，我们需要判断从第 sj 天到第 tj 天每天剩余的教室数量是否足够。我们可以使用一个循环从 sj 遍历到 tj，对于每一天，我们都判断 rooms[i] 是否大于等于 dj，如果不足够，则输出 -1 和订单的编号，然后结束程序。若足够，则将 rooms[i] 减去 dj，表示分配了 dj 个教室。/n/n如果所有订单都能够满足，则输出 0。/n/n## 算法步骤/n/n1. 读取输入的 n 和 m，初始化 rooms 数组为大小为 n 的全零数组。/n2. 读取 ri，并将其存入 rooms 数组中。/n3. 遍历每份订单：/n 1. 读取 dj、sj 和 tj。/n 2. 使用一个循环从 sj 遍历到 tj：/n 1. 判断 rooms[i] 是否小于 dj，如果是，则输出 -1 和订单的编号，然后结束程序。/n 2. 将 rooms[i] 减去 dj。/n4. 如果程序没有提前结束，则输出 0。/n/n## 代码实现/n/npython/nn, m = map(int, input().split())/nrooms = [0] * n/n/nfor i in range(n):/n rooms[i] = int(input())/n/nfor j in range(m):/n dj, sj, tj = map(int, input().split())/n for k in range(sj-1, tj):/n if rooms[k] < dj:/n print(-1)/n print(j+1)/n exit()/n rooms[k] -= dj/n/nprint(0)/n/n/n## 复杂度分析/n/n该算法遍历了每份订单，并在每份订单中遍历了从 sj 到 tj 的天数。因此，时间复杂度为 $O(m /cdot (t-s))$，其中 $m$ 是订单的数量，$s$ 和 $t$ 分别是订单的开始和结束天数。/n/n空间复杂度为 $O(n)$，用于存储每天可用的教室数量。/n