这是一道用前缀和与二分瞎搞的题。
原题链接：https://www.luogu.org/problem/show?pid=1083#sub
我们知道所有的订单，并且题目规定了所有订单必须从前往后依次处理。
题目要求输出最前面一个需要修改的订单号。
之前我们说，可以二分的题目需要满足解的有界性和单调性，此题显然满足。
有界性，需要修改的订单一定出现在[1,m]之间。
单调性，这是题目给的已知条件。
所以可以使用二分答案来求解这道题。
显然，它可以被认为是求“最大值最小”的问题。
我们在[1,m]上对答案进行二分，并且就暂且认为这一天会出问题。
那么如何判断这一天有没有出问题呢？
需要预处理一个前缀和数组sum，用来维护[1,mid]之间的需要房间总数。
这里可能不好想，对于一个sum，我们用order[i].st代表第i个订单的开始时间，order[i].ed为终止时间，order[i].room_num为这个订单内每天需要的房间数。
于是有
sum[order[i].st] += order[i].room_num;
sum[order[i].ed+1] -= order[i].room_num;
（对于i∈[1,mid]）
即开始在订单内的某天加上这一天所需要的房间数
订单外后的下一天减去那一天需要的房间数（因为这个时候已经借完了）
这时我们就处理好了某一天需要的总房间数。那么，枚举所有订单，寻找第一个不合法的订单，如果找到了不合法订单就返回true。所有订单都合法就返回false。
参考代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cctype> 5 #define maxn 1000005 6 using namespace std; 7 struct orders{ 8 int room_num; 9 int st; 10 int ed; 11 }; 12 orders order[maxn]; 13 int n,m; 14 int room_limit[maxn]; 15 int l,r,mid; 16 int sum[maxn]; 17 int read(){ 18 int num = 0; 19 char c; 20 bool flag = false; 21 while ((c = getchar()) == ' ' || c == ' ' || c == ' '); 22 if (c == '-') 23 flag = true; 24 else 25 num = c - '0'; 26 while (isdigit(c = getchar())) 27 num = num * 10 + c - '0'; 28 return (flag ? -1 : 1) * num; 29 } 30 31 bool judge(int mid){ 32 memset(sum,0,sizeof(sum)); 33 for (register int i=1;i<=mid;i++){ 34 sum[order[i].st] += order[i].room_num; 35 sum[order[i].ed+1] -= order[i].room_num; 36 } 37 for (register int i=1;i<=n;i++){ 38 sum[i]+=sum[i-1]; 39 if (sum[i]>room_limit[i]) 40 return true; 41 } 42 43 return false; 44 } 45 46 int main(){ 47 n = read();m = read(); 48 for (register int i=1;i<=n;i++) 49 room_limit[i] = read(); 50 for (register int i=1;i<=m;i++){ 51 order[i].room_num = read(); 52 order[i].st = read(); 53 order[i].ed = read(); 54 } 55 l=1;r=m; 56 while (l<r){ 57 mid=(l+r) >> 1; 58 if (judge(mid)) 59 r=mid; 60 else l=mid+1; 61 } 62 if (m!=r) 63 printf("-1 %d",r); 64 65 else 66 printf("0 "); 67 return 0; 68 }