首页 > 其他 > 详细

【题解】Luogu P1083 借教室

时间:2019-07-11 23:56:35      阅读:148      评论:0      收藏: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;
}

 

【题解】Luogu P1083 借教室

原文:https://www.cnblogs.com/gengyf/p/11173534.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!