[洛谷 1083][NOIP2012]借教室

题目链接

https://www.luogu.org/problem/P1083

题解

因为答案具有单调性（即假如前 \(x\) 个请求都能满足，则对于一切满足 \(y<x\) 的 \(y\)，前 \(y\) 个请求都能满足），考虑二分答案来解决。

检验时建出差分数组，从而在 \(O(n)\) 的时间内递推出每天需要的教室数量，并判断出能否满足相应数量的借教室申请。

#include <cstdio>
#include <cstring>
struct node
{
 int d,s,t;
}a[1000005];
int r[1000005],d[1000005],n,m;
bool check(int x)
{
 memset(d,0,sizeof(d));
 for(int i=1;i<=x;i++)
 {
  d[a[i].s]+=a[i].d;
  d[a[i].t+1]-=a[i].d;
 }
 int num=0;
 for(int i=1;i<=n;i++)
 {
  num+=d[i];
  if(num>r[i])return false;
 }
 return true;
}
int main()
{
 scanf("%d%d",&n,&m);
 for(int i=1;i<=n;i++)
  scanf("%d",&r[i]);
 for(int i=1;i<=m;i++)
  scanf("%d%d%d",&a[i].d,&a[i].s,&a[i].t);
 if(check(m))puts("0");
 else
 {
  puts("-1");
  int l=1,r=m;
  while(l<r)
  {
   int mid=(l+r)>>1;
   if(check(mid))l=mid+1;
   else r=mid;
  }
  printf("%d\n",l);
 }
 return 0;
}