【题解】Luogu P1083 借教室

亦凉 2021-11-17 15:02 252阅读 0赞

用差分数组(b\[i\])存每天教室的使用情况

所以当对区间操作时，其实可以转化成对b数组操作：

b[s[i]]+=d[i];
    b[t[i]+1]-=d[i];//d[i]是指每天要借的教室数

改变b\[i\]就相当于改变i之后的每一个值，并通过重新减去改变的量，达到操作区间的目的。

从第一份订单开始枚举，直到无法满足或者全枚举完结束。

另通过比大小来判断负数不容易出错

//
    //  main.cpp
    //  Luogu
    //
    //  Created by gengyf on 2019/7/11.
    //  Copyright © 2019 yifan Geng. All rights reserved.
    //
    
    #include <bits/stdc++.h>
    using namespace std;
    #define maxn 1000010
    int d[maxn],s[maxn],t[maxn];
    int b[maxn],n,m,need[maxn],a[maxn];
    bool check(int x){
        memset(b,0,sizeof(b));
        for(int i=1;i<=x;i++){
            b[s[i]]+=d[i];
            b[t[i]+1]-=d[i];
        }
        for(int i=1;i<=n;i++){
            need[i]=need[i-1]+b[i];
            if(need[i]>a[i])return 0;
        }
        return 1;
    }
    int main(){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        for(int i=1;i<=m;i++){
            scanf("%d%d%d",&d[i],&s[i],&t[i]);
        }
        int l=1,r=m;
        if(check(m)){
            printf("0\n");
            return 0;
        }
        while(l<r){
            int mid=(l+r)/2;
            if(check(mid)){
                l=mid+1;
            }
            else r=mid;
        }
        printf("-1\n%d",l);
        return 0;
    }

转载于:https://www.cnblogs.com/gengyf/p/11173534.html

发表评论取消回复

表情：

评论列表（有 0 条评论，252人围观）

还没有评论，来说两句吧...

相关阅读

相关题解 luogu P5021 【赛道修建】

题解 luogu P5021 【赛道修建】时间：2019.8.9 20:40 时间：2019.8.12 题目描述 C 城将要举办一系列的赛车比赛。在比赛前，需

今天药忘吃喽~/ 2023年10月09日 09:41/ 0 赞/ 33 阅读

相关【题解】Luogu P2831 愤怒的小鸟状压dp

状压dp -------------------- 思路来自[@real\_l][real_l] 由于抛物线$y=a\\{x^2\}+b\y$只有两个参数，初中数学老

桃扇骨/ 2023年08月17日 16:49/ 0 赞/ 139 阅读

相关 NOIP2012 借教室线段树

[题目链接][Link 1] 看这道题的时候，题目中的借教室我们可以看作是区间修改，如果有一天不符合的话都不行，第一反应就是线段树，维护最小值，查询的时候看是否满足要求，满足

一时失言乱红尘/ 2023年06月04日 08:00/ 0 赞/ 2 阅读

相关 luogu题解 P3388 【【模板】割点（割顶）】

外加定义：在一个无向图中，如果删掉点 x 后图的连通块数量增加，则称点 x 为图的割点。外加图示 ![图示][17909.png] 开始思路为割桥上的点为割点，后来证明

ゞ浴缸里的玫瑰/ 2022年01月05日 15:07/ 0 赞/ 259 阅读

相关二分前缀和借教室洛谷P1083

题目链接：[https://www.luogu.org/problemnew/show/P1083][https_www.luogu.org_problemnew_show_P

梦里梦外;/ 2021年11月29日 13:10/ 0 赞/ 182 阅读

相关【题解】Luogu P1083 借教室

用差分数组(b\[i\])存每天教室的使用情况所以当对区间操作时，其实可以转化成对b数组操作： b[s[i]]+=d[i]; b[t[i]+1]-=d[i

亦凉/ 2021年11月17日 15:02/ 0 赞/ 253 阅读

相关【题解】Luogu P5468 [NOI2019]回家路线

[原题传送门][Link 1] 前置芝士：斜率优化不会的可以去[杜神博客][Link 2]学这道题我考场上只会拆点跑最短路的70pts做法后来回家后发

水深无声/ 2021年10月30日 03:22/ 0 赞/ 338 阅读

相关【题解】Luogu P5337 [TJOI2019]甲苯先生的字符串

[原题传送门][Link 1] 我们设计一个\\(26\26\\)的矩阵\\(A\\)表示\\(a~z\\)和\\(a~z\\)是否能够相邻，这个矩阵珂以由\\(s1\

女爷i/ 2021年10月26日 16:31/ 0 赞/ 265 阅读

相关【题解】Luogu P5471 [NOI2019]弹跳

[原题传送门][Link 1] 先考虑部分分做法： subtask1：暴力\\(O(nm)\\)枚举，跑最短路 subtask2: 吧一行的点压到vecto

逃离我推掉我的手/ 2021年10月20日 00:20/ 0 赞/ 316 阅读

相关【题解】Luogu P2257 YY的GCD

[原题传送门][Link 1] 这题需要运用[莫比乌斯反演(懵逼钨丝繁衍)][Link 2] 显然题目的答案就是\\\[ Ans=\\sum\_\{i=1\}^N

た入场券/ 2021年10月01日 06:44/ 0 赞/ 281 阅读