星夜的蓝天

借教室[二分答案 zkw线段树] NOIP2012提高组复赛Day2T2
miku殿下11岁了呢,头图就选这个了。pid 64365538 先放题目 Description 在大学期间...
扫描右侧二维码阅读全文
08
2018/09

借教室[二分答案 zkw线段树] NOIP2012提高组复赛Day2T2

miku殿下11岁了呢,头图就选这个了。pid 64365538
miku赛高
先放题目

Description

在大学期间,经常需要租借教室。大到院系举办活动,小到学习小组自习讨论,都需要向学校申请借教室。教室的大小功能不同,借教室人的身份不同,借教室的手续也不一样。

面对海量租借教室的信息,我们自然希望编程解决这个问题。我们需要处理接下来n天的借教室信息,其中第i天学校有ri个教室可供租借。共有m份订单,每份订单用三个正整数描述,分别为dj,sj,tj,表示某租借者需要从第sj天到第tj天租借教室(包括第sj天和第tj天),每天需要租借dj个教室。
我们假定,租借者对教室的大小、地点没有要求。即对于每份订单,我们只需要每天提供dj个教室,而它们具体是哪些教室,每天是否是相同的教室则不用考虑。

借教室的原则是先到先得,也就是说我们要按照订单的先后顺序依次为每份订单分配教室。如果在分配的过程中遇到一份订单无法完全满足,则需要停止教室的分配,通知当前申请人修改订单。这里的无法满足指从第sj天到第tj天中有至少一天剩余的教室数量不足dj个。

现在我们需要知道,是否会有订单无法完全满足。如果有,需要通知哪一个申请人修改订单。

格式

输入格式

第一行包含两个正整数n,m,表示天数和订单的数量。
第二行包含n个正整数,其中第i个数为ri,表示第i天可用于租借的教室数量。
接下来有m行,每行包含三个正整数dj,sj,tj,表示租借的数量,租借开始、结束分别在第几天。
每行相邻的两个数之间均用一个空格隔开。天数与订单均用从1开始的整数编号。

输出格式

如果所有订单均可满足,则输出只有一行,包含一个整数0。否则(订单无法完全满足)输出两行,第一行输出一个负整数-1,第二行输出需要修改订单的申请人编号。

样例

样例输入1

4 3 
2 5 4 3 
2 1 3 
3 2 4 
4 2 4 

样例输出1

-1
2

限制

每个测试点1s

提示

对于10%的数据,有$1≤ n,m≤ 10$; 对于30%的数据,有$1≤ n,m≤1000$; 对于70%的数据,有$1≤ n,m≤ 10^5$; 对于100%的数据,有$1≤n,m≤10^6,0≤r_i,d_j≤10^9,1≤s_j≤t_j≤n$。

来源

Noip2012提高组复赛Day2T2

分析

对于这道题,我们可以直观的想到维护区间最小值,教室数少于0即无法满足该订单,那么直接暴力做法是可以拿30分的,但我们可以发现,随着订单数的增多,被用掉的教室数量肯定是只增不减的,也就是说,假设从第一个订单处理到第i个订单,我们发现教室数量都可以满足,那么,那个无法满足的订单,肯定是在第i天之后,即答案具有单调性,那么这个问题就可以转化为一个二分的问题,现在问题就变成如何快速判定从第一天到第i天的订单是否可以满足,考虑到只有判定需要用到我们维护的值,而模拟教室租借实际上只需要对区间进行更新,我们可以发现,实际上我们需要维护一个数组d[i],代表第i天已经租借出去的教室数量,每模拟一个订单$(d,s,t)$,我们就在s到t上加上d,而判定即枚举一遍数组,判断改天租借出去的数量是否小于该天可供租借的数量,一旦出现某一天的d大于room,即$d[i]>room[i]$,则该订单无法满足,但直接在原数组上进行区间更新的复杂度是$O(mn)$的,这显然不能接受,考虑到我们只需要判定一次,而更新需要很多次,我们可以利用拆分的思想,令$c[i]=d[i]-d[i-1]$,则$d[i]=\sum_{i=1}^n(c[i])$,则区间更新变为$c[s]=c[s]+d,c[t+1]=c[t+1]-d$,这样一来,区间更新就变为$O(1)$了,复杂度就可以接受了,实测,速度较快。以下是代码:

```c++
//noip2012 borrow room;

include

include

include

define NN 1000000+1

using namespace std;

int d[NN],s[NN],t[NN],f[NN];
int n,m;
int room[NN];

bool test(int num){
memset(f,0,sizeof(f));
for(int i=1;i<=num;i++){
f[s[i]]+=d[i];
f[t[i]+1]-=d[i];
}
int a=0;
for(int i=1;i<=n;i++){
a+=f[i];
if(a>room[i]){
return false;
}
};
return true;
}

int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for(int i=1;i<=n;i++){
cin >> room[i];
};

for(int i=1;i<=m;i++){
    cin >> d[i] >> s[i] >> t[i];
};
int l=1,r=n+1;
int ans=0;
while(l<=r){
    int mid=(l+r) >> 1;
    if(test(mid)==true){
        l=mid+1;
    } else{
        r=mid-1;
        ans=mid;
    }
};
if(ans==0){
    cout << 0 << endl;
} else{
    cout << -1 << endl<< ans << endl;
}

}


在vijos的测试结果上还算可以接受。

![](https://wx2.sinaimg.cn/large/005zWjpngy1fv2jnlg2pij30oc0m5wfv.jpg)

但如果只是维护区间最小值的话,我们其实还有一种思路,每次处理完一遍订单后进行判定,而区间更新我们可以使用线段树解决,复杂度为$O(Nlog_2 M)$,但实际上,由于查询得太过频繁,普通线段树在最后几个点会被活活卡死(毕竟不是正解),但是我们还有一种神奇的线段树啊,常数接近树状数组的**zkw线段树**,关于不了解**zkw线段树**的同学可以先去百度,我们将利用这个线段树维护区间最小值,并做到区间更新,区间查询,每处理一个订单就将第s天到第t天的可租借教室减去d,直到出现一个最小值为负数,证明这个订单无法满足,实测,**zkw线段树**的效率甚至会快于二分答案,代码如下:

> ~~2018/10/20更新:下面的代码的区间查询函数为闭区间版本,不符合zkw原本的开区间写法,且代码较长,修改后的版本在文章末尾。~~
>
> 更新后的开区间写法只是碰巧在出错几率不超过$\frac{1}{2^n}$的情况下查询到了全局最小值而已,碰巧A掉了所有的点,请大家不要模仿,好好的写闭区间吧。

```c++
//重写借教室 基于ZWK线段树
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int c[4000008*2];
int cnt;
int ls,rt,va;
void build(){
    for(m=1;m<n+2;m<<=1);
    for(int i=m+1;i<=m+n;i++){
        cin >> c[i];
    }
    int temp=0;
    for(int i=(m+n)/2;i;i--){
        temp=min(c[i+i],c[i+i+1]);
        c[i+i]-=temp;
        c[i+i+1]-=temp;
        c[i]+=temp;
    }
}
void change(int s,int t,int value){
    int temp=0;
    for(s=s+m-1,t=t+m+1;s^t^1;s>>=1,t>>=1){
        if(~s&1)c[s^1]+=value;
        if(t&1)c[t^1]+=value;
        temp=min(c[s],c[s^1]),c[s]-=temp,c[s^1]-=temp,c[s>>1]+=temp;
        temp=min(c[t],c[t^1]),c[t]-=temp,c[t^1]-=temp,c[t>>1]+=temp;
    }
    for(;s>1;s>>=1){
        temp=min(c[s],c[s^1]);c[s]-=temp;c[s^1]-=temp;c[s>>1]+=temp;
    }
}
bool ask(int s,int t,int v=0){
    if (s==t){
        s=s+m;
        int res=0;
        while(s>1)res+=c[s>>=1];
        return res>=0;
    }
    int lans=0;
    int rans=0;
    for(s=s+m,t=t+m;s^t^1;s>>=1,t>>=1){
        lans+=c[s];
        rans+=c[t];
        if(~s&1)lans=min(lans,c[s^1]);
        if(t&1)rans=min(rans,c[t^1]);
    }
    int res = min(lans,rans);
    while(s>1)res+=c[s>>=1];
    if (res<v) return false;
    return true;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    build();
    while(k--){
        cnt++;
        cin >> va >> ls >> rt;
        change(ls,rt,-va);
        if (ask(ls,rt)==false){
            cout << "-1" << endl;
            cout << cnt << endl;
            return 0;
        }
    }
    cout << "0" << endl;
    return 0;
}

测评结果如下:

2018/10/20更新:开区间写法,顺便在此指出《统计的力量》原PPT的一处错误,即区间查询开区间写法中的lans与rans的初值应赋为闭区间的左右端点,而非开区间的左右端点,请自行对比《统计的力量》标记永久化中的写法和如下ask函数的不同。不过zkw的开区间写法还是错的……这点倒是没错。

反正是查询整体最小值,直接看根节点c[1]就好了嘛,ask函数都可以不用写了,少了20行代码呢。

//重写借教室 基于ZWK线段树
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int c[4000008*2];
int cnt;
int ls,rt,va;
void build(){
    for(m=1;m<n+2;m<<=1);
    for(int i=m+1;i<=m+n;i++)
        cin >> c[i];
    int temp=0;
    for(int i=(m+n)/2;i;i--){
        temp=min(c[i+i],c[i+i+1]);
        c[i+i]-=temp;
        c[i+i+1]-=temp;
        c[i]+=temp;
    }
}
void change(int s,int t,int value){
    int temp=0;
    for(s=s+m-1,t=t+m+1;s^t^1;s>>=1,t>>=1){
        if(~s&1)c[s^1]+=value;
        if(t&1)c[t^1]+=value;
        temp=min(c[s],c[s^1]),c[s]-=temp,c[s^1]-=temp,c[s>>1]+=temp;
        temp=min(c[t],c[t^1]),c[t]-=temp,c[t^1]-=temp,c[t>>1]+=temp;
    }
    for(;s>1;s>>=1)
        temp=min(c[s],c[s^1]),c[s]-=temp,c[s^1]-=temp,c[s>>1]+=temp;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    int np=k;
    build();
    while(k--){
        cnt++;
        cin >> va >> ls >> rt;
        change(ls,rt,-va);
        if (c[1]<0){
            cout << "-1" << endl;
            cout << cnt << endl;
            return 0;
        }
    }
    cout << "0" << endl;
    return 0;
}
最后修改:2018 年 11 月 01 日 11 : 55 PM
如果觉得我的文章对你有用,请随意赞赏

发表评论

召唤看板娘