题目内容

P1083

解题思路

嗯,这道题一看,暴力枚举

分析:这道题满足二分答案,为什么:

我们将订单挨个标号,很显然,订单越多,越难满足要求,这满足二分答案要求的单调性。我们只需将订单挨个枚举即可。

二分的答案是订单的标号,订单越多越到后面越不能满足,因此很容易找到那个”1″和”0″的分界,使用一个check函数即可判断。

至于check函数的实现,这里使用了差分的重要思想。每一个订单会给出起始时间s和末尾时间t,相当于在[s,t]这段时间内多租借d个教室,很像区间加问题。所以我们定义一个数组c存储需要使用的教室的差分,处理每个订单的时候就c[s[i]]+=d[i],c[t[i]+1]-=d[i]注意是t[i]+1,并且是-=,已掉坑不止5次。然后将差分数组加起来(求前缀和)判断这么多个订单能否满足能提供教室的条件,返回即可。

代码实现:

#include <cstdio>
#include <cstring>
#define f(i,a,b) for(int i=a;i<=b;++i)

const int maxn=1e6+5;
int n,m,r[maxn],d[maxn],s[maxn],t[maxn],diff[maxn];//r,d,s,t见题意,diff为差分数组

inline int read()//我喜欢快读
{
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}

bool check(int mid)
{
    memset(diff,0,sizeof(diff));//每次使用的时候要清零差分数组
    f(i,1,mid)
        diff[s[i]]+=d[i],diff[t[i]+1]-=d[i];//操作差分数组实现区间加
    int ans=0;//记录前缀和
    f(i,1,n)
    {
        ans+=diff[i];//每次加起来
        if(ans>r[i])//如果不能满足需要
            return 0;
    }
    return 1;//否则return true
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
#endif
    n=read(),m=read();
    f(i,1,n)
        r[i]=read();
    f(i,1,m)
        d[i]=read(),s[i]=read(),t[i]=read();
    //以上读入数据
    int l=1,r=m;//开始二分
    while(l<r)//mid越大越难不挨卡
    {
        int mid=l+r>>1;
        if(check(mid))//如果满足要求
            l=mid+1;//说明mid可能还可以更大
        else
            r=mid;//否则mid就太大了
    }
    if(r!=m)//如果r!=m的话说明不能满足所有订单
        printf("-1\n%d\n",r);
    else//否则可以满足所有订单
        printf("0\n");
    return 0;
}

反思

蓝题,果然在二分的思维比较难,而且二分答案的代码细节非常多。

下次再写一波

最后修改日期:2020年1月30日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。