题目描述
无
样例
无
算法1
(二分+差分) $O(nlgn)$
第一想法 区间修改 想到线段树 下方附带线段树解
第二就是差分+二分 二分答案 找一个没出错的最小值
注意的是二分结果如果为1 要讨论1和2谁是正确的 边界问题
差分来维护区间修改
时间复杂度
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N =1000010 ;
int n,m;
ll a[N];
ll b[N];
ll d[N];
struct{
ll d;
int s,t;
}c[N];
void insert(int l,int r,ll c)
{
d[l]-=c;
d[r+1]+=c;
}
bool check(int res)
{
memcpy(d,b,sizeof(b));
for(int i=1;i<=res;i++)
{
insert(c[i].s,c[i].t,c[i].d);
}
int ans=0;
for(int i=1;i<=n;i++)
{
ans+=d[i];
if(ans<0)return false;
}
return true;
}
int main()
{
cin>>n>>m;//n天 m个订单
for(int i=1;i<=n;i++)
{cin>>a[i];
b[i]+=a[i];//差分数组构造完成
b[i+1]-=a[i];
}
for(int i=1;i<=m;i++)
{
ll x; int y,z;
cin>>x>>y>>z;
c[i]={x,y,z};
}
int l=1,r=m;
while(l<r)
{
int mid=l+r+1>>1;
if(check(mid))l=mid;
else
r=mid-1;
}
if(r==m) puts("0");
else
{
printf("-1\n");
if(r==1)//因为可能是第二天有问题 二分找一个正确的结果
{ int l=c[1].s;int r=c[1].t;
b[l]-=c[1].d;
b[r+1]+=c[1].d;
int abc=0;
for(int i=1;i<=n;i++)
{
abc+=b[i];
if(abc<0){cout<<1<<endl;return 0;}
}
cout<<2<<endl;
}
else
cout<<l+1<<endl;
}
return 0;
}
算法2
(线段树模板)
为什么可以套线段树
本质上就是维护区间最小值
C++ 代码
#include<bits/stdc++.h>
#define N 1000006
using namespace std;
int n,m;
int R[N];
int MIN[N*8];
int lazy[N*8];
void down(int x){
if(lazy[x]){
MIN[x*2]-=lazy[x];
MIN[x*2+1]-=lazy[x];
lazy[x*2]+=lazy[x];
lazy[x*2+1]+=lazy[x];
lazy[x]=0;
}
}
void buit(int bh,int l,int r)
{
if(l==r){
MIN[bh]=R[r];
return;
}
int mid=(l+r)/2;
buit(bh*2,l,mid);
buit(bh*2+1,mid+1,r);
MIN[bh]=min(MIN[bh*2],MIN[bh*2+1]);
}
int ask(int bh,int l,int r,int cl,int cr)
{
down(bh);
if(cl<=l&&r<=cr){
return MIN[bh];
}
int mid=(l+r)/2,ans=INT_MAX;
if(cl<=mid) ans=min(ans,ask(bh*2,l,mid,cl,cr));
if(cr>mid) ans=min(ans,ask(bh*2+1,mid+1,r,cl,cr));
MIN[bh]=min(MIN[bh*2],MIN[bh*2+1]);
return ans;
}
void xg(int bh,int l,int r,int cl,int cr,int k)
{
down(bh);
if(cl<=l&&r<=cr){
MIN[bh]-=k;
lazy[bh]+=k;
return;
}
int mid=(l+r)/2;
if(cl<=mid) xg(bh*2,l,mid,cl,cr,k);
if(cr>mid) xg(bh*2+1,mid+1,r,cl,cr,k);
MIN[bh]=min(MIN[bh*2],MIN[bh*2+1]);
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
scanf("%d",&R[i]);
buit(1,1,n);
for(int i=1;i<=m;i++)
{
int d,s,t;
scanf("%d%d%d",&d,&s,&t);
int M=ask(1,1,n,s,t);
if(M>=d){
xg(1,1,n,s,t,d);
}else{
puts("-1");
cout<<i<<"\n";
return 0;
}
}
puts("0");
return 0;
}
支持博主