题解 P1083 【借教室】
题解

为啥都是前缀和,差分不是更显而易见么?

考虑维护各天剩余教室数量,差分后区间减时只用dt[l]-=c, dt[r+1]+=c。

然后从第一天开始累加dt[],即某一天剩余教室数量,若<0,就从第m个请求开始撤销(区间加),同时--m,此时注意区间与当前天的关系,具体看代码for里面的if。

最终n天扫完,此时m即为满足n天剩余教室均非负的最大请求数,加1即为答案,当然若等于原m需输出0。

由于m单调不增,时空复杂度均为O(n+m)

代码中使用了指针而不是直接--m

const int N = 1000003;
const int M = 1000003;
struct Q_{int c,l,r;}ss[M], *sp = ss;
int w[N]; ll dt[N];

int main()
{
  int n = i_(), m = i_();
  for(int i = 1; i <= n; ++i) dt[i] = (w[i] = i_())-w[i-1];
  for(int i = 1; i <= m; ++i)
  {
    int c = i_(), l = i_(), r = i_();
    *sp++ = (Q_){c, l, r};
    dt[l] -= c, dt[r+1] += c;
  }
  ll cur = 0;
  for(int i = 1; i <= n; ++i)
    for(cur += dt[i]; cur < 0 && --sp; )
      if(sp->l > i) dt[sp->l] += sp->c, dt[sp->r+1] -= sp->c;
      else if(sp->r >= i) cur += sp->c, dt[sp->r+1] -= sp->c;
  if(sp-ss == m) puts("0");
  else printf("-1\n%d\n", (int)(sp-ss)+1);
  return 0;
}
评论