【题解】Luogu P1083 借教室

亦凉 2021-11-17 15:02 221阅读 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 条评论，221人围观）

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

相关阅读

相关【题解】Luogu P1038 神经网络拓扑排序

topsort 板(?)题显然，题目要求从入度为零的点遍历到出度为零的点，想到用拓排另如果是输入层，那么u\[i\]为1或0都没有关系，一定会激活同时处理出度便于输

小咪咪/ 2023年08月17日 16:49/ 0 赞/ 91 阅读

相关【题解】Luogu P3942 将军令贪心

f\[x\]\[0\] 表示最近控制驿站的距离 f\[x\]\[1\]表示最远不能控制的驿站距离当f\[x\]\[0\]+f\[x\]\[1\]≤k是说明能被控制，但没有

- 日理万妓/ 2023年08月17日 16:49/ 0 赞/ 87 阅读

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

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

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

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

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

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

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

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

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

相关【题解】Luogu P1083 借教室

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

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

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

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

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

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

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

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

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

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

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

相关【题解】Luogu P2257 YY的GCD

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

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