洛谷P1083借教室题解

这个难度感觉并没有那么高，因为这个题暴力也好打，但是比较难想出正解，因为如果你不看标签是很难想到这个题竟然是二分，当然前缀和应该很好想，毕竟让你求的是在某段时间内借教室的和是否满足。

这样我们可以很容易的推出借的教室的个数和订单是成正对应的，因此他可以满足单调性，所以我们就可以用上二分。

而原题中我们可以把天数看成x轴上的横坐标，这天的借教室数可以看成y轴上的纵坐标，而每一次订单的增加，我们就要让从第一个订单到这个订单中的所有订单都加起来，这就像一个区间修改，然后我们在判断的时候就需要用到单点查询这天满不满足。

因此我们可以想到差分数组和前缀和的结合，然后再搭配二分，就ok了。

代码：

// luogu-judger-enable-o2

#include<iostream>

#include<cstring>

#include<cstdio>

#define M 1000010

using namespace std;

struct cym {

    int l ,r, d;

} e[M];

int delta[M], sum[M], nul[M], n, m;

bool flag;

bool check(int x) {

    memset(delta, , sizeof(delta));

    for(int i = ; i <= x; i++) {

        delta[e[i].l] += e[i].d;

        delta[e[i].r + ] -= e[i].d;

    }

    for(int i = ; i <= n; i++) {

        sum[i] = sum[i - ] + delta[i];

        if(sum[i] > nul[i])

            return false;

    }

    return true;

}

int main() {

    scanf("%d%d", &n, &m);

    for  (int i = ; i <= n; i++)

        scanf ("%d", &nul[i]);

    for (int i = ; i <= m; i++)

        scanf ("%d%d%d", &e[i].d, &e[i].l, &e[i].r);

    for(int i = ; i <= m; i++) {

        delta[e[i].l] += e[i].d;

        delta[e[i].r + ] -= e[i].d;

    }

    for(int i = ; i <= n; i++) {

        sum[i] = sum[i - ] + delta[i];

        if(sum[i] > nul[i])

            flag = ;

    }

    if(!flag)

    {

        printf("");

        return ;

    }

    int left = , right = m;

    while (left < right) {

        int mid = (left+right) / ;

        if (check(mid))

            left = mid + ;

        else

            right = mid;

    }

    printf ("-1\n%d", left);

}

巴特西

洛谷P1083借教室题解

最新文章

热门文章