题解 P1083 【借教室】
安利一发自己的博客：http://www.cnblogs.com/OIerShawnZhou/
（我平常写的题解都会往博客里发，欢迎各位大佬前来拍砖）
这是一道用前缀和与二分瞎搞的题。
我们知道所有的订单，并且题目规定了所有订单必须从前往后依次处理。
题目要求输出最前面一个需要修改的订单号。
之前我们说，可以二分的题目需要满足解的有界性和单调性，此题显然满足。
有界性，需要修改的订单一定出现在[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。
参考代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#define maxn 1000005
using namespace std;
struct orders{
int room_num;
int st;
int ed;
};
orders order[maxn];
int n,m;
int room_limit[maxn];
int l,r,mid;
int sum[maxn];
int read(){
int num = 0;
char c;
bool flag = false;
while ((c = getchar()) == ' ' || c == '\n' || c == '\r');
if (c == '-')
flag = true;
else
num = c - '0';
while (isdigit(c = getchar()))
num = num * 10 + c - '0';
return (flag ? -1 : 1) * num;
}
bool judge(int mid){
memset(sum,0,sizeof(sum));
for (register int i=1;i<=mid;i++){
sum[order[i].st] += order[i].room_num;
sum[order[i].ed+1] -= order[i].room_num;
}
for (register int i=1;i<=n;i++){
sum[i]+=sum[i-1];
if (sum[i]>room_limit[i])
return true;
}
return false;
}
int main(){
n = read();m = read();
for (register int i=1;i<=n;i++)
room_limit[i] = read();
for (register int i=1;i<=m;i++){
order[i].room_num = read();
order[i].st = read();
order[i].ed = read();
}
l=1;r=m;
while (l<r){
mid=(l+r) >> 1;
if (judge(mid))
r=mid;
else l=mid+1;
}
if (m!=r)
printf("-1\n%d",r);
else
printf("0\n");
return 0;
}