题解38 [NOIP2012 提高组] 借教室

前言：具有二分性质，在处理到某个人时，教室数量突然就<0，然后就不能再处理请求了。将处理的订单数作为二分枚举对象依旧是一道二分+验证的题,并且同前缀和与差分结合起来（注意：涉及到对区间大量的+-操作，一定不能直接操作，而是要维护一个差分数组，不然时间直接爆表）

思路&AC代码：

#include<iostream>
#include<cstring>//memcpy()
using namespace std;
int room[1000010];
int delta[1000010];
int tmpd[1000010];
int n;
struct ty
{
    int d,s,t;
}deal[1000010];
bool judge(int x)
{
  	//另一种写法memcpy(tmpd+1,delta+1,n*sizeof(delta[1]));相当于把delta[1]到delta[n]复制到tmpd[1]到tmpd[n];memcpy(复制到的地址，原地址，总字节长度);数组名+1指向数组名[1]元素所在的地址
    memcpy(tmpd,delta,sizeof(delta));//sizeof(数组名)，等于数组所占总的字节数
  //也可循环赋值，因为每次传入的x不同，不能让修改重复了
    for(int i=1;i<=x;++i)
    {
        tmpd[deal[i].s]-=deal[i].d;//差分
        tmpd[(deal[i].t)+1]+=deal[i].d;
    }
    int sum=0;//教室总数最大1e9
    for(int i=1;i<=n;++i)
    {
        sum+=tmpd[i];//前缀和
        if(sum<0) {return false;}//小于0说明没空教室了
    }
    return true;
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    int m;cin>>n>>m;
    delta[0]=0;
    for(int i=1;i<=n;++i) {cin>>room[i];delta[i]=room[i]-room[i-1];}//delta:第i天房间数减前一天房间数
  
  //也可直接在原数组上差分，节省空间=>room[0]=0;for(int i=n; i>=1; i--) room[i] -= room[i-1];
    for(int i=1;i<=m;++i) {cin>>deal[i].d>>deal[i].s>>deal[i].t;}
    int l=0,r=m,mid;//最少处理0份订单，最多全处理完
    while(l<r)
    {
        mid=(l+r+1)>>1;//类比于求满足<=x的最后一个
        if(judge(mid)) {l=mid;}
        else {r=mid-1;}
    }
    if(l==m) {cout<<0;}
    else {cout<<l+1;}//<=x符合要求的最后一个+1就是第一个不符合要求（取不到的）人
  //另一种二分写法
    /*while(l<r)
    {
        mid=(l+r)>>1;
        if(!judge(mid)) {r=mid;}//取不到的话，第一个取不到的人就是右界，最后退出循环的时候l==r就是第一个取不到的人
        else {l=mid+1;}//能取到的话就再往右边试试，第一个取不到的人就是左界，最后退出循环的时候l==r就是第一个取不到的人
    }
    if(l==m) {cout<<0;}
    else {cout<<l;}*/
    return 0;
}