借教室
题目 借教室
思路分析
因为订单依次进行
若第三个订单不满足 则第四个订单一定不满足 若第二个订单满足 则第一个订单一定满足
存在二段性 所以可以用二分（暴力tle了才想到 不应该……）
处理订单就是对某一段减去d 可以想到用差分
判断订单完成与否就是看经过处理后的差分数组变成前缀和后是否教室数为负
可以转换成 把这俩步拆开来
处理需要借的教室 和 实际有的教室
如果需要借的教室大于实际有的教室 就不满足
那就从每段区间-c变成了+c
省去了还原b[]状态的麻烦
代码实现
暴力 tle: 11/23
m个订单依次执行 直到某次教室数为负了说明本次订单存在问题
问题在于check本次订单是否符合时 都会重新构建一次前缀和
如果订单在很靠后的情况才失败 就会超时
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long LL;
const int N=1e6+10;
LL a[N],b[N],s[N];
int n,m;
void insert(int l,int r,LL c){
b[l]-=c;
b[r+1]+=c;
}
bool check(){
memset(s,0,sizeof s);
for(int i=1;i<=n;i++){
s[i]=s[i-1]+b[i];
if(s[i]<0)
return false;
}
return true;
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
insert(i,i,-a[i]);
}
for(int i=1;i<=m;i++){
LL d; int s,t;
cin>>d>>s>>t;
insert(s,t,d);
if(!check()){
cout<<"-1"<<endl<<i<<endl;
return 0;
}
}
cout<<"0"<<endl;
return 0;
}
二分 ac
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long LL;
const int N=1e6+10;
LL a[N],b[N],D[N];
int S[N],T[N];
int n,m;
void insert(int l,int r,LL c){
b[l]+=c;
b[r+1]-=c;
}
bool check(int m){
memset(b,0,sizeof b);
for(int i=1;i<=m;i++)
insert(S[i],T[i],D[i]);
for(int i=1;i<=n;i++){
b[i]+=b[i-1];
if(b[i]>a[i])
return true;
}
return false;
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=m;i++) cin>>D[i]>>S[i]>>T[i];
int l=1,r=m+1;
while(l<r){
int m=l+r>>1;
if(check(m)) r=m;
else l=m+1;
}
if(r==m+1)
cout<<"0"<<endl;
else
cout<<"-1"<<endl<<r<<endl;
return 0;
}
💬 评论