二分前缀和借教室洛谷P1083

梦里梦外; 2021-11-29 13:10 221阅读 0赞

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

题意：一共有n天，每天可提供Ri个教室，有m份订单，每份订单是从第Si天到第Ji天，借Di个教室，问是否能借完。

分析：一开始想着用线段树，但是线段树在区间更新的时候并不是一个个更新，而是将一整个区间的值改变，对应的点想要查询时再将lazy标记下放，用线段树会非常慢，故不用线段树。

这里有一篇非常好的博客：[https://pks-loving.blog.luogu.org/post-2012-d2-t2-jie-jiao-shi-ti-xie][https_pks-loving.blog.luogu.org_post-2012-d2-t2-jie-jiao-shi-ti-xie]

在这里提炼下内容：

差分是前缀和数组的逆运算

**前缀和是用元数据求元与元之间的并集关系，而差分则是根据元与元之间的逻辑关系求元数据，是互逆思想**

是否能二分的界定标准是：**状态的决策过程或者序列是否满足单调性或者可以局部舍弃性。** 而在这个题里，因为如果前一份订单都不满足，那么之后的所有订单都不用继续考虑；而如果后一份订单都满足，那么之前的所有订单一定都可以满足，符合局部舍弃性，所以可以二分订单数量。（不太好懂，看代码就能理解）

注意：need数组是独立于rest数组的，diff数组是服务于need数组的，diff\[i\]数组是need\[i\]-need\[i-1\]，我们利用差分方便的进行修改，最后求出need数组与rest数组做比较（不要轻易相减以防出现re）

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int inf=0x3f3f3f3f;//这个数是1e9数量级的，且可以用memset函数 
    const int maxn=1e6+7;
    const double pi=acos(-1);
    const int mod=1e9+7;
    int rest[maxn],d[maxn],l[maxn],r[maxn],diff[maxn],need[maxn];
    int n,m;
    
    bool isok(int x){
        //用来判断前x份订单需不需要进行修改 
        memset(diff,0,sizeof(diff));
        for(int i=1;i<=x;i++){
            diff[l[i]]+=d[i];
            diff[r[i]+1]-=d[i];
        }
        for(int i=1;i<=n;i++){
            need[i]=need[i-1]+diff[i];
            if(need[i]>rest[i]){
                return 0;
            }
        }
        return 1;
    }
    
    int main(){
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            scanf("%d",&rest[i]);
        }
        for(int i=1;i<=m;i++){
            scanf("%d%d%d",&d[i],&l[i],&r[i]);
        }
        if(isok(m)){cout<<0<<endl;return 0;}
        int left=1,right=m;
        while(left<right){
            int mid=(left+right)/2;
            if(isok(mid))left=mid+1;
            else right=mid;
        }
        cout<<-1<<endl<<right<<endl;
        return 0;
    }

转载于:https://www.cnblogs.com/qingjiuling/p/11217025.html

[https_www.luogu.org_problemnew_show_P1083]: https://www.luogu.org/problemnew/show/P1083
[https_pks-loving.blog.luogu.org_post-2012-d2-t2-jie-jiao-shi-ti-xie]: https://pks-loving.blog.luogu.org/post-2012-d2-t2-jie-jiao-shi-ti-xie