洛谷P1083 借教室 (差分数组+二分)

题目链接**

题意是给定你一个天数n和借教室的订单m，然后接下来n个数给定你每天的空闲教室量。然后m行中有三个数分别表示订单所需的教室数量以及开始和结束时间。如果所有订单均可满足，则输出只有一行，包含一个整数 0。否则（订单无法完全满足）输出两行，第一行输出一个负整数−1，第二行输出需要修改订单的申请人编号。

刚开始看到这个题时，首先想到的是暴力求解，依次对每个订单进行操作，将订单的区间里的所有教室数减去需求量，如果教室数小于0时结束并打印结果。这样的话复杂度爆炸，肯定是不行的。接下来想到对区间进行修该以及查询常用的方法线段树，但是线段树代码量太大容易出bug，有不有什么更简单的方法呢？后来本蒟蒻了解到了差分数组这种东西。

首先考虑这样一个问题，如果求区间（x，y）的和，比较高效的方法是先求出区间的前缀和然后相减来得到结果。差分数组其实就是前缀和的逆运算。对于区间（x，y），差分数组d[i]=a[i]-a[i-1]，那么我们得到a[x]=d[1]+d[2]+d[3]+…d[x]。对于区间（x，y）的修改（比如加c），我们只需将d[x]+=c，以及d[y+1]-=c，想一想是不是这样？每次更新完之后我们需要用前缀和的思想来求得每个数组新的值。

介绍完差分数组之后我们再回来看这道题，如果前k个订单满足条件，那么我们就得考虑后面的订单，如果前k个订单不满足条件，那么我们就得从前k个订单中找答案，于是我们想到了二分的方法。对于每次二分，我们用一个差分数组来记录前k个的情况，让每个订单的左边界的差分数组加上该订单的需求量，让每个订单的右边界+1的差分数组减去该订单的需求量。然后再前缀和求出前k天每天的需求量，然后再进行判断，判断的O(n*m)的复杂度就变成了O(n+m)

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int maxn=1000007;
int l[maxn],r[maxn],need[maxn],rest[maxn],d[maxn],num[maxn];
bool check(int cur)
{
    memset(d,0,sizeof(d));
    for(int i=1;i<=cur;i++)
    {
        d[l[i]]+=num[i];
        d[r[i]+1]-=num[i];
    }
    for(int i=1;i<=n;i++)
    {
        need[i]=need[i-1]+d[i];
        if(need[i]>rest[i])
        return 0;
    }
    return 1;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    scanf("%d",&rest[i]);
    for(int i=1;i<=m;i++)
    scanf("%d%d%d",&num[i],&l[i],&r[i]);
    int left=1,right=m,mid;
    if(check(m))
    {
        printf("0\n");
        return 0;
    }
    while(left<right)
    {
        mid=(left+right)>>1;
        if(check(mid)) left=mid+1;
        else right=mid;
    }
    printf("-1\n%d\n",left);
    return 0;
}