借教室（二分答案 + 差分）

心得：
1.二分答案要充分理解输出Left与输出Right的含义，分别时返回尽可能小的答案值(return l)和尽可能大的答案值(return r)。

2.二分答案步骤
step one：确定所求答案具有单调性，则可以使用二分答案(或者看到出现最大值最小或最小值最大之类的问题)
step two：写check函数，相当于是将可能的答案带入验证该答案是否满足题目的性质

#include 
#include 
#include 
using namespace std;
const int N = 1e6 + 10;
int line[N], l[N], r[N], d[N], change[N];
int n, m;


bool check(int x)
{
	memset(change,0,sizeof(change));
	for (int i = 1; i <= x; i++)
	{
		change[l[i]] += d[i];
		change[r[i] + 1] -= d[i];
		//用差分数组对前x个操作进行处理
	}
    //抹平差分数组
	for (int i = 1; i <= n; i++) change[i] += change[i - 1];

	for (int i = 1; i <= n; i++)
		if(change[i] > line[i])
            return false;//订单所申请的房间量无法被满足

	return true;
}
//本题读入数据量较大，要用scanf较好
int main()
{
    scanf("%d%d",&n,&m);
	for (int i = 1; i <= n; i++) scanf("%d", &line[i]);
	for (int i = 1; i <= m; i++) scanf("%d%d%d", &d[i], &l[i], &r[i]);

	if(check(m))//全都可以成立的情况
	{
		puts("0");
		return 0;
	}

	int left = 1, right = m, mid;
	while(left <= right)
	{
		mid = (left + right) >> 1;
		if(check(mid)) left = mid + 1;
		else right = mid - 1;
	}
	puts("-1");
	cout << left << 'n';//能容纳的最小的订单量即为修改订单的申请人编号

	return 0;
}