题目描述
_借教室的原则是先到先得,也就是说我们要按照订单的先后顺序依次为每份订单分配教室。
如果在分配的过程中遇到一份订单无法完全满足,则需要停止教室的分配,通知当前申请人修改订单。
第二行就可以分析到二分的二段性,在那个临界点订单前面的可以满足后面的不可以,
第一行可以知道先到先得,在一段区间上修改一个范围的值使用差分
有一点写的可以简洁一些,其实不用构造差分数组,直接通过差分计算每天的教室需求量来比较教室当天的剩余量进行check,这样的话可以节省3行代码;
注意最后输出的时候不能用二分的右边界直接等于订单数来判断,有可能最后一个订单不满足,我就是这么被卡掉的
我看了很多人写的代码,发现还是y总的最简洁,下面我是按着他的样子写的
样例
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=1e6+6;
ll r[N],d[N],r1[N];
int s[N],t[N];
int n,m;
bool check(int mid)
{
memset(r1,0,sizeof r1);
for(int i=1;i<=mid;i++)
{
r1[s[i]]+=d[i];
r1[t[i]+1]-=d[i];
}
ll res=0;
for(int i=1;i<=n;i++)
{
res+=r1[i];
if(res>r[i])
return false;
}
return true;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)scanf("%d",&r[i]);
for(int i=1;i<=m;i++)scanf("%d%d%d",&d[i],&s[i],&t[i]);
int l=1,r=m;
while(l<r)
{
int mid=l+r>>1;
if(check(mid))l=mid+1;
else r=mid;
}
if(check(m))puts("0");
else printf("-1\n%d\n",l);
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla