csp信奥赛C++高频考点专项训练之前缀和差分 --【一维差分】：[NOIP 2012 提高组] 借教室
csp信奥赛C++高频考点专项训练之前缀和&差分 --【一维差分】：[NOIP 2012 提高组] 借教室
题目描述
在大学期间，经常需要租借教室。大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。
面对海量租借教室的信息，我们自然希望编程解决这个问题。
我们需要处理接下来n nn天的借教室信息，其中第i ii天学校有r i r_iri个教室可供租借。共有m mm份订单，每份订单用三个正整数描述，分别为d j , s j , t j d_j,s_j,t_jdj,sj,tj，表示某租借者需要从第s j s_jsj天到第t j t_jtj天租借教室（包括第s j s_jsj天和第t j t_jtj天），每天需要租借d j d_jdj个教室。
我们假定，租借者对教室的大小、地点没有要求。即对于每份订单，我们只需要每天提供d j d_jdj个教室，而它们具体是哪些教室，每天是否是相同的教室则不用考虑。
借教室的原则是先到先得，也就是说我们要按照订单的先后顺序依次为每份订单分配教室。如果在分配的过程中遇到一份订单无法完全满足，则需要停止教室的分配，通知当前申请人修改订单。这里的无法满足指从第s j s_jsj天到第t j t_jtj天中有至少一天剩余的教室数量不足d j d_jdj个。
现在我们需要知道，是否会有订单无法完全满足。如果有，需要通知哪一个申请人修改订单。
输入格式
第一行包含两个正整数n , m n,mn,m，表示天数和订单的数量。
第二行包含n nn个正整数，其中第i ii个数为r i r_iri，表示第i ii天可用于租借的教室数量。
接下来有m mm行，每行包含三个正整数d j , s j , t j d_j,s_j,t_jdj,sj,tj，表示租借的数量，租借开始、结束分别在第几天。
每行相邻的两个数之间均用一个空格隔开。天数与订单均用从1 11开始的整数编号。
输出格式
如果所有订单均可满足，则输出只有一行，包含一个整数0 00。
否则（订单无法完全满足）输出两行，第一行输出一个负整数− 1 -1−1，第二行输出需要修改订单的申请人编号。
输入输出样例 1
输入 1
4 3 2 5 4 3 2 1 3 3 2 4 4 2 4输出 1
-1 2说明/提示
【输入输出样例说明】
第1 11份订单满足后，4 44天剩余的教室数分别为0 , 3 , 2 , 3 0,3,2,30,3,2,3。第2 22份订单要求第2 22天到第4 44天每天提供3 33个教室，而第3 33天剩余的教室数为2 22，因此无法满足。分配停止，通知第2 22个申请人修改订单。
【数据范围】
对于10 % 10\%10%的数据，有1 ≤ n , m ≤ 10 1\le n,m\le 101≤n,m≤10；
对于30 % 30\%30%的数据，有1 ≤ n , m ≤ 1000 1\le n,m\le 10001≤n,m≤1000；
对于70 % 70\%70%的数据，有1 ≤ n , m ≤ 10 5 1 \le n,m \le 10^51≤n,m≤105；
对于100 % 100\%100%的数据，有1 ≤ n , m ≤ 10 6 1 \le n,m \le 10^61≤n,m≤106，0 ≤ r i , d j ≤ 10 9 0 \le r_i,d_j\le 10^90≤ri,dj≤109，1 ≤ s j ≤ t j ≤ n 1 \le s_j\le t_j\le n1≤sj≤tj≤n。
思路分析
本题需要按照订单顺序判断教室资源是否足够。直接模拟会超时（n , m ≤ 10 6 n,m \le 10^6n,m≤106）。
核心方法：二分答案 + 差分数组。
- 二分第一个不满足的订单编号
pos，使得前pos-1个订单都能满足，而第pos个订单无法满足。 - 判断函数
check(mid)：计算前mid个订单每天所需教室总数，与初始资源r[i]比较。使用差分数组diff实现区间加，然后求前缀和得到每天总需求。 - 若所有订单都满足，输出
0；否则输出-1和第一个不满足的订单编号。
复杂度：O((n+m) log m)，空间O(n+m)。
代码实现
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintN=1e6+5;intn,m;// n天数，m订单数intr[N];// 第i天可用教室数intd[N],s[N],t[N];// 订单：数量，开始，结束ll diff[N];// 差分数组（暂存需求）// 判断前mid个订单是否都能满足boolcheck(intmid){memset(diff,0,sizeof(ll)*(n+2));// 初始化差分数组for(inti=1;i<=mid;++i){// 区间加diff[s[i]]+=d[i];// 开始加diff[t[i]+1]-=d[i];// 结束减}ll cur=0;// 当前天总需求for(inti=1;i<=n;++i){cur+=diff[i];// 求前缀和得到第i天总需求if(cur>r[i])returnfalse;// 超过可用教室数}returntrue;}intmain(){scanf("%d%d",&n,&m);for(inti=1;i<=n;++i)scanf("%d",&r[i]);for(inti=1;i<=m;++i)scanf("%d%d%d",&d[i],&s[i],&t[i]);intL=1,R=m+1;// 二分范围：[1, m+1)，若答案为m+1表示全满足while(L<R){intmid=(L+R)/2;if(check(mid))L=mid+1;// 前mid个满足，尝试更多elseR=mid;// 不满足，缩小右边界}if(L==m+1)printf("0\n");// 所有订单都满足elseprintf("-1\n%d\n",L);// 第一个不满足的订单编号return0;}功能分析
- 输入处理：使用
scanf快速读入数据（避免cin超时）。 - 差分数组：
diff[s[i]] += d[i]、diff[t[i]+1] -= d[i]实现区间加，最后通过前缀和得到每天总需求。 - 二分判定：
check(mid)函数返回前mid个订单是否可行，复杂度O(n+mid)。 - 二分答案：在
[1, m+1]区间内二分查找第一个不满足的位置。若最终L == m+1则全部满足，否则输出-1和L。 - 空间优化：差分数组动态清零，只使用
O(n)额外空间。 - 边界条件：注意
t[i] + 1可能等于n+1，数组大小开至n+2避免越界。
【完整系列请查看专栏】：
信奥赛C++普及组CSP-J一等奖通关刷题题单及题解：
https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转
各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}【秘籍汇总】（完整csp信奥赛C++学习资料）：
1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：
https://edu.csdn.net/lecturer/7901 点击跳转
2、CSP信奥赛C++竞赛拿奖视频课：
https://edu.csdn.net/course/detail/40437 点击跳转
https://edu.csdn.net/course/detail/41081 点击跳转
3、csp信奥赛高频考点知识详解及案例实践：
CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转
CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转
信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转
4、csp信奥赛冲刺一等奖有效刷题题解：
信奥赛C++普及组CSP-J一等奖通关刷题题单及题解：
https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转
信奥赛C++提高组csp-j初赛&复赛真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转
5、GESP C++考级真题题解：
GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转
GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转
GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}