洛谷1083 [NOIP2012]借教室

题意

有 $N$ 天，每天剩余教室为 $R_i$ 个。有 $M$ 个人要借教室，从 $S_i$ 借到 $T_i$ 。问能否满足所有人，如果不行则输出第一个不满足的人。

$N,M\le 10^6$ 。

题解

本来还想写线段树查询最小值的，然后发现二分+差分就能解决。

做法就是二分答案，然后差分修改后验证是否有 $<0$ 的。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

const int N=1000005;
int n,m,a,b,r[N],d[N],s[N],t[N],cur[N];

inline bool check(int mid)
{
    memcpy(cur,r,sizeof(r));
    for (int i=1;i<=mid;i++)
    {
        cur[s[i]]-=d[i];
        cur[t[i]+1]+=d[i];
    }
    int res=0;
    for (int i=1;i<=n;i++) if ((res+=cur[i])<0) return 0;
    return 1;
}

signed main()
{
    n=read(); m=read();
    for (int i=1;i<=n;i++)
    {
        a=read();
        r[i]=a-b;
        b=a;
    }
    for (int i=1;i<=m;i++) d[i]=read(),s[i]=read(),t[i]=read();
    int l=0,r=n+1;
    while (l<r)
    {
        int mid=(l+r)>>1;
        if (check(mid)) l=mid+1;
        else r=mid;
    }
    if (r==n+1) return 0&puts("0");
    return !printf("-1\n%d",l);
}