题目链接
这题思维难度总体来说不大,整体的思路是比较清晰明了的。

45分解法

首先根据题目要求,我们应该不难得到一个45分的解法:
遍历每个订单,并且对于原数组进行减法操作,当某一个地方为0,那么就说明该订单不ok,然后输出-1与当前订单号。

代码

#include<cstdio>
#include<queue>
#include<cstring>
#include<cmath>
using namespace std;
inline int read()
{
    int neg=1,x=0;
    char ch;
    while((ch=getchar())<'0'||ch>'9')
        if(ch=='-')
            neg=-1;
    x=ch-'0';
    while((ch=getchar())>='0'&&ch<='9')
        x=x*10+(ch-'0');
    return x*neg;
}
int n,m,d[1000005],r[1000005],s[1000005],t[1000005];
int main()
{
    n=read(),m=read();
    for(register int i=1;i<=n;i++)
    {
        r[i]=read();
    }
    for(register int i=1;i<=m;i++)
    {
        d[i]=read(),t[i]=read(),s[i]=read();
        for(register int j=t[i];j<=s[i];j++)
        {
            r[j]-=d[i];
            if(r[j]<0)
            {
                printf("%d\n",-1);
                printf("%d",i);
                return 0;
            }
        }
    }
    printf("%d",0);
    return 0;
}

100分解法

然后考虑优化,如果稍有数据结构基础的话,看到区间做减法,第一时间联想到的就应该是线段树/树状数组,然而蒟蒻我果断地想到了用树状数组维护差分数组,这样可以在log级别的时间内维护减法,然而问题在于……如果我们这样维护的话,45分解法里面的循环嵌套是舍不掉的……也就是说只优化了常数,对复杂度贡献最大的那一部分依然没有优化。
然后开始考虑其他方法,这个时候我们再读一下题,发现要求修改的那一个订单是最先不满足要求的,那么同理可得那份之前的订单都是满足题意的。也就是说,答案域单调!那么我们就可以二分答案啦。但是之前想到的差分数组就莫得用了吗?不是的,我们可以通过维护差分数组c,来对区间进行操作(这里就把复杂度优化了鸭),下面贴上代码.

代码

#include<cstdio>
#include<queue>
#include<cstring>
#include<cmath>
using namespace std;
inline int read()
{
    int neg=1,x=0;
    char ch;
    while((ch=getchar())<'0'||ch>'9')
        if(ch=='-')
            neg=-1;
    x=ch-'0';
    while((ch=getchar())>='0'&&ch<='9')
        x=x*10+(ch-'0');
    return x*neg;
}
int sum,ans,lr,ri,mid,c[1000005],n,m,d[1000005],r[1000005],s[1000005],t[1000005];
inline bool check(int x)
{
    sum=0;
    memset(c,0,sizeof(c));
    for(register int i=1;i<=x;i++)
    {
        c[t[i]]+=d[i];
        c[s[i]+1]-=d[i];
    }
    for(register int i=1;i<=n;i++)
    {
        sum=sum+c[i];
        //printf("%d %d\n",dn[i],c[i]);
        if(sum>r[i])
            return false;
    }
    return true;
}
int main()
{
    n=read(),m=read();
    for(register int i=1;i<=n;i++)
    {
        r[i]=read();
    }
    for(register int i=1;i<=m;i++)
    {
        d[i]=read(),t[i]=read(),s[i]=read();
    }
    lr=1,ri=m;
    if(check(m))
    {
        printf("0");
        return 0;
    }//如果全都满足
    while(lr<=ri)
    {
        mid=(lr+ri)>>1;
        if(check(mid))
        {
            lr=mid+1;
        }
        else
        {
            ri=mid-1;
        }
    }
    printf("%d\n",-1);
    printf("%d",lr);

    return 0;
}