题目内容
解题思路
嗯，这道题一看，暴力枚举
分析：这道题满足二分答案，为什么：
我们将订单挨个标号，很显然，订单越多，越难满足要求，这满足二分答案要求的单调性。我们只需将订单挨个枚举即可。
二分的答案是订单的标号，订单越多越到后面越不能满足，因此很容易找到那个”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;
}
反思
蓝题，果然在二分的思维比较难，而且二分答案的代码细节非常多。
下次再写一波
留言