【题解】Luogu P1083 借教室

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

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

相关阅读

相关题解 luogu P1850 【换教室】

题解 luogu P1850 【换教室】时间：2019.8.6 一晚上（约 3.5h 写完）题目描述对于刚上大学的牛牛来说，他面临的第一个问题是如何根据实际

Dear 丶/ 2023年10月09日 09:42/ 0 赞/ 76 阅读

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

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

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

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

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

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

相关借教室

[https://vijos.org/p/1782][https_vijos.org_p_1782] 描述在大学期间，经常需要租借教室。大到院系举办活动，小到学习小组

秒速五厘米/ 2023年06月29日 14:58/ 0 赞/ 30 阅读

相关 luogu P1311 选择客栈题解

\\(luogu\\) P1311 选择客栈题解 [题目链接][Link 1] 看到这道题目首先很茫然，一看统计方案数，肯定要什么数论或者数学知识吧，然后就打了个暴力

小咪咪/ 2023年06月01日 15:54/ 0 赞/ 62 阅读

相关题解 Luogu P3959 【宝藏】

来一篇不那么慢的状压？？？话说这题根本没有紫题难度吧，数据还那么水我是不会告诉你我被hack了 -------------------- 一看数据规模，n≤12，果

布满荆棘的人生/ 2023年06月01日 12:42/ 0 赞/ 45 阅读

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

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

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

相关【题解】Luogu P1083 借教室

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

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

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

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

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

相关【题解】Luogu P2257 YY的GCD

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

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