P1083 借教室 差分数组

时间:2022-12-19 17:28:19

  

第一行包含两个正整数n,mn,m,表示天数和订单的数量。

第二行包含nn个正整数,其中第ii个数为r_iri,表示第ii天可用于租借的教室数量。

接下来有mm行,每行包含三个正整数d_j,s_j,t_jdj,sj,tj,表示租借的数量,租借开始、结束分别在第几天。

每行相邻的两个数之间均用一个空格隔开。天数与订单均用从11开始的整数编号。

 

输出格式:

 

如果所有订单均可满足,则输出只有一行,包含一个整数00。否则(订单无法完全满足)

输出两行,第一行输出一个负整数-11,第二行输出需要修改订单的申请人编号。

 

输入输出样例

输入样例#1:  复制
4 3 
2 5 4 3 
2 1 3 
3 2 4 
4 2 4
输出样例#1:  复制
-1 
2

说明

【输入输出样例说明】

第 11份订单满足后,44天剩余的教室数分别为 0,3,2,30,3,2,3。第 22 份订单要求第 22天到第 44 天每天提供33个教室,而第 33 天剩余的教室数为22,因此无法满足。分配停止,通知第22 个申请人修改订单。

 

差分数组   和前缀和差不多  维护区间增减情况

 

而所谓的差分数组,即是前缀和数组的逆运算:

我们给定前i个数相邻两个数的差(1<=i<=n),求每一项a[i](1<=i<=n)。

此时无非就是用作差的方式求得每一项,此时我们可以有一个作差数组diff,diff[i]用于记录a[i]-a[i-1],然后对于每一项a[i],我们可以递推出来:

for(int i=1;i<=n;i++) {cin>>diff[i];a[i]=diff[i]+a[i-1];} for(int i=1;i<=n;i++) {cout<<a[i];}

其次,要知道差分会起到怎样的作用:因为diff数组决定着每个元数据的变化大小、趋势,所以,当我们想要针对区间操作时,钱可以转化成对diff数组操作:

diff[l[i]]+=d[i];
diff[r[i]+1]-=d[i];//d[i]是指每天要借的教室数

 

P1083 借教室 差分数组P1083 借教室 差分数组
#include<bits/stdc++.h>
using namespace std;
//input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);--i)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m)
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define ll long long
#define pb push_back
#define CLR(A,v)  memset(A,v,sizeof A)
//////////////////////////////////////
#define inf 0x3f3f3f3f
#define lson l,m,pos<<1
#define rson m+1,r,pos<<1|1
const int N=5e6+5;
int a[N],differ[N],n,m,ans,L,R,d[N],l[N],r[N],need[N];

bool ok(int x)
{
    CLR(differ,0);
    rep(i,1,x)
    differ[l[i]]+=d[i],differ[r[i]+1]-=d[i];

    rep(i,1,n)
    {
        need[i]=need[i-1]+differ[i];
        if(need[i]>a[i])return 0;
    }
    return 1;
}
int main()
{
    RII(n,m);
    rep(i,1,n)RI(a[i]);
    L=0;R=n;

    rep(i,1,m)
    RIII(d[i],l[i],r[i]);
    if(ok(n)){return cout<<"0",0;}
    while(L<=R)
    {
        int m=(L+R)>>1;
        if(ok(m))ans=m,L=m+1;
        else R=m-1;
    }
    cout<<"-1"<<endl;
    cout<<ans+1;

    return 0;
}
View Code