借教室
问题描述:本题用到的算法包括差分和二分,其中比较难想到的是:二分订单,即订单从1~m,寻找满足
订单的最大编号的下一项,或者找出不满足订单的最小编号并输出。如果从题目输出要求下手,可大致
理解二分订单的含义。
在主函数中,输入要求按题目要求进行,之后进行二分订单。本人设置的二分截至点:满足订单的最大编号,如果小于m即输出为最大编号+1,否则说明订单均满足要求。之后就是调用bool型check函数:mid是1~m之间的点,也就是找到满足题意的编号。每次调用check,必须要使f数列清零(f数组为差分数组),不能让上一次的结果影响这一次。接下来的for循环会从第一组编号到mid进行计算(对f数组进行差分计算),之后for循环进行f数组还原,比较题目原始每天能提供的房间数量,如果满足,则true,否则false。
注:
1、check函数中,第一个for循环中f数组是差分数组,第二个for循环中f数组进行还原,数据为订单编号从1~mid所有的需要的最小房间数量。
2、至于进入check函数一开始对f数组进行清零操作,是因为f数组最终的数据是所需最小的房间量。
3、考虑到d数组的最大值为1e9,可能会爆int,使用typedef对longlong简化为ll,但是数组r范围也是1
e9,为啥使用int型,我是没弄明白?可能是测试数据少的原因吧。
时间复杂度分析:
二分,时间复杂度O(logm); 差分,时间复杂度O(n+m)。最终为二者乘积:O( (n+m)logm )。
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=1e6+10;
int n,m;
int w[N],d[N],s[N],t[N];
typedef long long LL;
LL f[N];
//int f[N];
bool check(int a)
{
memset(f, 0, sizeof f);//每次操作需先把发f[N]清零,上一次的结果不能影响下一次,具体看下一个for循环,从头开始累加
for(int i=1;i<=a;i++)
{
f[s[i]] += d[i];
f[t[i]+1] -= d[i];
}
for(int i=1;i<=n;i++)
{
f[i]=f[i]+f[i-1];
if(f[i]>w[i]) return false;
}
return true;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>w[i];
}
for(int i=1;i<=m;i++)
{
cin>>d[i]>>s[i]>>t[i];
}
int l=0,r=m;
while(l<r)
{
int mid=(l+r+1)/2;
if(check(mid)) l=mid;
else r=mid-1;
}
if( r == m ) cout<<0;
else cout<<-1<<"\n"<<r+1;
return 0;
}