洛谷 P1083 借教室 （差分，二分）

差分数组和二分法
本题要点：
1、对订单数 进行二分，找到刚好第k条订单教室不过分。

2、差分数组 pre[i] 表示前i条订单， 每个教室的需求总数的总和 的差分。一开始，pre数组置零；
每次计算前 mid 条订单，对于某个区间[L, R]的教室的需求量加上d, 相当于 第 L个教师加上d,
第 R + 1 个教室减去 d;

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MaxN = 1000010;
int pre[MaxN], r[MaxN], d[MaxN], s[MaxN], t[MaxN];
int n, m;bool judge(int mid)	//找到第一个不满足条件的订单
{
    r[0] = 0;memset(pre, 0, sizeof(pre));for(int i = 1; i <= mid; ++i){
    pre[s[i]] += d[i];pre[t[i] + 1] -= d[i];}int sum = 0;for(int i = 1; i <= n; ++i){
    sum += pre[i];if(sum > r[i])	//教室不够, 不满足条件{
    return true;}}return false;
}void solve()
{
    int L = 1, R = m + 1, mid;while(L < R){
    mid = (L + R) / 2;if(judge(mid)){
    R = mid;}else{
    L = mid + 1;}}
// printf("L = %d\n", L);if(L == m + 1){
    printf("0\n");	}else{
    printf("-1\n");printf("%d\n", L);}
}int main()
{
    scanf("%d%d", &n, &m);for(int i = 1; i <= n; ++i){
    scanf("%d", &r[i]);}for(int i = 1; i <= m; ++i){
    scanf("%d%d%d", &d[i], &s[i], &t[i]);}solve();return 0;
}/* 4 3 2 5 4 3 2 1 3 3 2 4 4 2 4 *//* -1 2 */