题解 P1083 【借教室】

chen_zhe · 2016-11-27 17:18:44 · 题解

因为是求哪个订单先，并且看这奇葩数据范围，二分妥妥（线段树神犇不要坑人）

例如下面的这个样例：

4 3 2 5 4 3

2 1 3 3 2 4 4 2 4 我们可以把开始天+租借数量

结束天后面的那一天-租借数量

接下来就无脑循环一遍，检查哪一个订单超过了可以租借的数量

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 1000005

using namespace std;

int LEFT,MID,RIGHT,n,m,r[maxn],d[maxn],s[maxn],t[maxn],day[maxn];

bool judge(int mid)
{
    memset(day,0,sizeof(day));
    for (int i=1;i<=mid;i++)
    {
        day[s[i]]+=d[i];
        day[t[i]+1]-=d[i];
    }
    if (day[1]>r[1])
        return 1;
    for (int i=2;i<=n;i++)
    {
        day[i]+=day[i-1];
        if (day[i]>r[i])
            return 1;
    }
    //cout << -1 << endl;
    return 0;
}

int main()
{
    //freopen("classroom.in","r",stdin);
    //freopen("classroom.ans","w",stdout);
    cin >> 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]);
    LEFT=1;RIGHT=m;
    while (LEFT<RIGHT)
    {
        MID=(LEFT+RIGHT)/2;
        //cout << LEFT << " " << RIGHT << " " << MID << endl;
        if (judge(MID))
            RIGHT=MID;
        else LEFT=MID+1;
    }    
    if (m!=RIGHT) 
    {
        cout << -1 << endl;
        cout << RIGHT << endl;
    }
    else cout << 0 << endl;
    return 0;
}